結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー IJMP320
提出日時 2015-03-02 01:07:44
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,182 bytes
コンパイル時間 1,923 ms
コンパイル使用メモリ 168,924 KB
実行使用メモリ 813,900 KB
最終ジャッジ日時 2024-06-24 00:53:28
合計ジャッジ時間 5,156 ms
ジャッジサーバーID
（参考情報） 		judge1 / 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<nord*,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(&g[b],c));
		g[b].connect.push_back(make_pair(&g[a],c));
	}

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

	int n=S;
	while(true) {
		if(n==G) {
			printf("%d\n",g[n].id);
			break;
		}
		else {
			printf("%d ",g[n].id);
		}
		n = g[n].from;
	}

	return 0;
}
0