はやし屋

競技プログラミングのメモ きたない

aoj 0244: Hot Spring Trip

さっきからちょっと休憩してやった

二個飛ばしはすぐ浮かんだ

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; ++i)
struct edge {
  int t , c;
  edge(int t , int c): t(t) , c(c){};
};
struct P {
  int n,c,tic;
  P(int n , int c , int tic): n(n) , c(c) , tic(tic) {};
};

bool operator >(const P& l , const P& r){
  return l.c > r.c;
}

int n, m;
vector < edge > edges[111];
int cc[111][3];

void init(){
  rep(i,111){
    edges[i].clear();
    rep(k,3){
      cc[i][k] = 1 << 27;
    }
  }
}

void dij(){
  priority_queue < P , vector < P > , greater < P > > que;
  // start tic
  que.push(P(0,0,1));
  cc[0][0] = cc[0][1] = 0;

  while(!que.empty()){
    P p = que.top();que.pop();

    rep(i,edges[p.n].size()){
      edge t = edges[p.n][i];
      if(p.c+t.c < cc[t.t][p.tic]){
	cc[t.t][p.tic] = p.c+t.c;
	que.push(P(t.t,p.c+t.c,p.tic));
      }

// 二個飛ばし
      if(p.tic){
	rep(j,edges[t.t].size()){
	  edge tt = edges[t.t][j];
	  if(p.c < cc[tt.t][0]){
	    cc[tt.t][0] = p.c;
	    que.push(P(tt.t,p.c,0));
	  }
	}
      }

    }
  }
}

int main(){
  while(cin >> n >> m&&(n|m)){
    init();
    rep(i,m){
      int a,b,c;cin >> a >> b >> c;
      --a , --b;
      edges[a].push_back(edge(b,c));
      edges[b].push_back(edge(a,c));
    }
    dij();
    int r = min(cc[n-1][1] , cc[n-1][0]);
    cout << r << endl;
  }
}