結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 WA -
testcase_04 AC 5 ms
6,940 KB
testcase_05 AC 8 ms
6,944 KB
testcase_06 AC 10 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<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