結果

問題 No.160 最短経路のうち辞書順最小
ユーザー IJMP320IJMP320
提出日時 2015-03-02 01:07:44
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 WA -
testcase_04 AC 5 ms
6,944 KB
testcase_05 AC 8 ms
6,940 KB
testcase_06 AC 12 ms
6,944 KB
testcase_07 MLE -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
権限があれば一括ダウンロードができます

ソースコード

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