結果

問題 No.160 最短経路のうち辞書順最小
ユーザー IJMP320
提出日時 2015-03-02 00:44:29
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,267 bytes
コンパイル時間 1,797 ms
コンパイル使用メモリ 170,828 KB
実行使用メモリ 813,908 KB
最終ジャッジ日時 2024-06-24 00:51:59
合計ジャッジ時間 5,199 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 3 MLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pint;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const int INF = 100000000;
const int dx[4]={0,1,0,-1}, dy[4]={-1,0,1,0};
struct P{int x;int y;P(int X=0,int Y=0){x=X;y=Y;}};

struct nord{
	int id;
	vector< pair<int,int> > connect; // id,cost
	int cost;
	int from;
};

int main() {
	int N,M,S,G;
	cin >> N >> M >> S >> G;
	vector<nord> g;
	g.resize(N);
	rep(i,N) {g[i].id = i; g[i].cost = INF; g[i].from = -1;}
	rep(i,M) {
		int a,b,c;
		cin >> a >> b >> c;
		g[a].connect.push_back(make_pair(b,c));
		g[b].connect.push_back(make_pair(a,c));
	}

	queue<int> q;
	q.push(S);
	g[S].cost = 0;
	while(!q.empty()) {
		int n=q.front(); q.pop();
		int num = g[n].connect.size();
		rep(i,num) {
			if(g[ g[n].connect[i].first ].cost >= g[n].connect[i].second + g[n].cost) {
				g[ g[n].connect[i].first ].from = g[n].id;
				g[ g[n].connect[i].first ].cost = g[n].connect[i].second + g[n].cost;
				q.push(g[n].connect[i].first);
			}
		}
	}

	vector<int> ans;
	int n=G;
	while(true) {
		ans.push_back(n);
		if(n==S) break;
		n=g[n].from;
	}

	int as = ans.size();
	for(int i=as-1; i>=0; i--) {
		printf("%d",ans[i]);
		if(i==0) putchar('\n');
		else putchar(' ');
	}

	return 0;
}
0