読者です 読者をやめる 読者になる 読者になる

UVa11833 Route Change

問題
http://uva.onlinejudge.org/external/118/11833.html

概要は原文を確認してください。

解法

#include <bits/stdc++.h>
  
using namespace std;
  
#define MAX (250)
#define INF (1<<29)
  
typedef pair<int, int> Pii;

struct Edge { int to, cost; };
vector<Edge> G[MAX];

int dist[MAX];

int N, M, C;

int dijkstra(int S, int T) {
  priority_queue<Pii, vector<Pii>, greater<Pii> > PQ;
  fill(dist, dist+MAX, INF);
  dist[S] = 0;
  PQ.push(Pii(0, S));
  
  while(!PQ.empty()) {
    Pii pii = PQ.top(); PQ.pop();
    const int u = pii.second;
    const int cost = pii.first;
    for(int i=0; i<(int)G[u].size(); i++) {
      const Edge& e = G[u][i];
      if(u < C && e.to != u+1) continue;
      if(dist[e.to] > dist[u]+e.cost) {
	dist[e.to] = dist[u]+e.cost;
	PQ.push(Pii(dist[e.to], e.to));
      }
    }
  }
  
  return dist[T];
}
  
  
int main(){
  
  int K;
  while(cin >> N >> M >> C >> K && (N|M|C|K)){
    for(int i=0; i<MAX; i++) G[i].clear();
    int a, b, c;
    for(int i=0; i<M; i++){
      cin >> a >> b >> c;
      G[a].push_back((Edge){b, c});
      G[b].push_back((Edge){a, c});
    }
    
    cout << dijkstra(K, C-1) << endl;
  }
  
  return 0;
}