ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 0244 Hot Spring Trip

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0244


・概要
箇条書きにする以下のような感じです。
・グラフが与えられます
・各ノード間には料金が設定されています
・2つの区間の料金を無料にできる切符を一枚だけ持っています
。そのときのある出発地から目的地に到達するまでにかかる最少料金を求める問題です。

詳しくは問題文をご覧下さい。


・解法
拡張ダイクストラ法で解くことができます。

この問題の重要なポイントは、上の箇条書きに書いた3つ目の内容です。
そのことを考慮して解いていきます。
キューにはpair<コスト、pair<現在値、切手の枚数>>を持たせます。

下のソースコードはわりとさっぱり書けたんじゃないかなぁーと個人的に思っています。


ソースコード

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<cstring>
using namespace std;

#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n) REP(i,0,n)

#define f first
#define s second
#define mp make_pair
#define pb push_back
typedef pair<int, pair<int,int> > P;
//pair<コスト、pair<現在値、切手の枚数>>

struct Edge{
   int to, cost;
   Edge(int _to, int _cost):to(_to), cost(_cost){};
};

int n,m;
int minCost[100][2];
vector<Edge> edge[100];
static const int INF = (1 << 29);

int bfs(){
   priority_queue<P, vector<P>, greater<P> >pq;
   pq.push(mp(0,mp(0,1)));
   rep(i,n)rep(j,2)minCost[i][j] = INF;

   while(!pq.empty()){
      P p = pq.top();
      pq.pop();
      
      if(p.s.f==n-1)return p.f;

      if(minCost[p.s.f][p.s.s] <= p.f)continue;
      minCost[p.s.f][p.s.s] = p.f;

      rep(i,edge[p.s.f].size()){
	 Edge e = edge[p.s.f][i];
	 pq.push(mp(p.f+e.cost, mp(e.to, p.s.s)));
	 
	 if(p.s.s==0)continue;
	 rep(j,edge[e.to].size()){
	    Edge ee = edge[e.to][j];
	    pq.push(mp(p.f, mp(ee.to, 0)));
	 }
      }
   }
   return -1;
}

int main(){
   while(cin >> n >> m){
      if(n==0 && m==0)break;

      rep(i,n)edge[i].clear();

      rep(i,m){
	 int a,b,c;
	 cin >> a >> b >> c;
	 edge[a-1].pb(Edge(b-1,c));
	 edge[b-1].pb(Edge(a-1,c));
      }
      
      cout << bfs() << endl;
   }
   return 0;
}