結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー ciel
提出日時 2015-03-09 18:13:27
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 7 ms / 5,000 ms
コード長 1,538 bytes
コンパイル時間 561 ms
コンパイル使用メモリ 51,200 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-24 16:54:41
合計ジャッジ時間 1,558 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:45:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   45 |         scanf("%d%d%d%d",&V,&E,&r,&x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:49:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   49 |         for(;E--;)scanf("%d%d%d",&s,&t,&e),g[s].push_back(Edge(s,t,e)),g[t].push_back(Edge(t,s,e));
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 999999999
using namespace std;

typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void shortestPath(const Graph &g, int s,
    vector<Weight> &dist, vector<int> &prev) {
  int n = g.size();
  dist.assign(n, INF); dist[s] = 0;
  prev.assign(n, -1);
  priority_queue<Edge> Q; // "e < f" <=> "e.weight > f.weight"
  for (Q.push(Edge(-2, s, 0)); !Q.empty(); ) {
    Edge e = Q.top(); Q.pop();
    if (prev[e.dst] != -1) continue;
    prev[e.dst] = e.src;
    for(auto &f:g[e.dst]) {
      if (dist[f.dst] > e.weight+f.weight) {
        dist[f.dst] = e.weight+f.weight;
        Q.push(Edge(f.src, f.dst, e.weight+f.weight));
      }
    }
  }
}

int main(){
	int r,x,i,V,E,s,t,e;
	scanf("%d%d%d%d",&V,&E,&r,&x);
	Graph g(V);
	vector<Weight> dist;
	vector<int> prev;
	for(;E--;)scanf("%d%d%d",&s,&t,&e),g[s].push_back(Edge(s,t,e)),g[t].push_back(Edge(t,s,e));
	shortestPath(g,x,dist,prev);
	for(printf("%d",r);r!=x;){
		int next=1<<29;
		for(auto &e:g[r]){
			if(dist[r]==dist[e.dst]+e.weight)next=min(next,e.dst);
		}
		r=next;
		printf(" %d",r);
	}
	puts("");
}
0