結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー srup٩(๑`н´๑)۶
提出日時 2016-06-22 10:35:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,454 bytes
コンパイル時間 948 ms
コンパイル使用メモリ 81,100 KB
実行使用メモリ 265,852 KB
最終ジャッジ日時 2024-10-11 19:16:47
合計ジャッジ時間 7,648 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3 OLE * 1
other -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<pint> vpint;
#define mp make_pairt
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)

//ダイクストラ法を用いた、最短経路とその経路を求めるライブラリ
const int INF = 1e9;
const int MAX_V = 210;//頂点の数
int cost[MAX_V][MAX_V];//cost[u][v]は辺e=(u, v)のコスト(存在しない場合はINF)
int d[MAX_V];//頂点sからの最短距離
bool used[MAX_V];//すでに使われたかどうかのフラグ
int V;//頂点数
int prv[MAX_V];//最短路の直前の頂点

int s, g;

//始点sから各頂点への最短経路を求める
void dijkstra(int s){//始点を引数に
	//初期化
	fill(d, d + V, INF);
	fill(used, used + V, false);
	fill(prv, prv + V, -1);
	d[s] = 0;

	while(true){
		int v = -1;
		//まだ使われてない頂点の内、距離が最小のものを選ぶ
		for(int u = 0; u < V; u++){
			if(!used[u] && (v == -1 || d[u] < d[v])) v = u;
		}

		if(v == -1) break;
		used[v] = true;

		for(int u = 0; u < V; u++){
			if(d[u] > d[v] + cost[v][u]){
				d[u] = d[v] + cost[v][u];
				prv[u] = v;
			}
			//最短経路を復元する必要がない場合
			//d[u] = min(d[u], d[v] + cost[v][u]);
		}
	}
	return;	
}

//頂点tへの最短路
vector<int> get_path(int t){//引数でゴールを渡す
	prv[s] = -1;
	vector<int> path;
	for(; t != -1; t = prv[t]){
		printf("t: %d\n", t);
		path.push_back(t);//tがsになるまで、prv[t]を巡っていく
	}
	//このままだと、t->sの順位なっているので、逆順にする
	reverse(path.begin(), path.end());
	return path;
}

int main(void){
	int n, m;
	scanf("%d%d%d%d", &n, &m, &s, &g);
	//大きめの数字で初期化
	rep(i, 210)rep(j, 210) cost[i][j] = cost[j][i] = INF;
	//同じ時点は0
	rep(i, 210) cost[i][i] = 0;
	//入力
	rep(i, m){
		int a, b, c;
		scanf("%d%d%d", &a,&b,&c);
		//a--; b--; //0オリジンへ
		cost[a][b] = cost[b][a] = c;//無向グラグ　2つに代入すること
	}

	dijkstra(s);
	vector<int> ans = get_path(g);
	int size = ans.size();
	rep(i, size) printf("%d ", ans[i]);
	printf("\n");

	return 0;		
}
0