結果

問題 No.160 最短経路のうち辞書順最小
ユーザー SHIJOUSHIJOU
提出日時 2020-08-19 01:33:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 7 ms / 5,000 ms
コード長 2,437 bytes
コンパイル時間 2,604 ms
コンパイル使用メモリ 221,100 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 03:26:25
合計ジャッジ時間 4,028 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

struct edge {
	int to;
	int64_t cost;
	edge(int x=0, int64_t y=0):to(x), cost(y) {}
};

vector<vector<edge> > G; // resizeの必要あり

struct dijkstra {
	vector<int64_t> d;
	dijkstra(int s, int n):d(n, INT64_MAX/3) { // sはスタート,nは頂点数
		d[s] = 0LL;
		priority_queue<pair<int64_t, int>, vector<pair<int64_t, int> >, greater<pair<int64_t, int> > > que;
		que.push(make_pair(0LL, s));
		while(!que.empty()) {
			pair<int64_t, int> now = que.top();
			que.pop();
			if(now.first != d[now.second]) continue;
			for(edge next:G[now.second]) {
				if(d[next.to] > d[now.second] + next.cost) {
					d[next.to] = d[now.second] + next.cost;
					que.push(make_pair(d[next.to], next.to));
				}
			}
		}
	}
	int64_t &operator[](int idx) {return d[idx];}
	const int64_t &operator[](int idx) const {return d[idx];}
};

//head

int n, m, s, g;
vi gg[210];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> s >> g;
	G.resize(n);
	rep(i, m) {
		int a, b, c;
		cin >> a >> b >> c;
		G[a].emplace_back(b, c);
		G[b].emplace_back(a, c);
	}
	dijkstra D(s, n);

	queue<int> q;
	q.emplace(g);
	while(!q.empty()) {
		int now = q.front();
		q.pop();
		rep(i, G[now].size()) {
			int ne = G[now][i].to;
			if(D[ne] != D[now]-G[now][i].cost) continue;
			if(gg[ne].empty()) q.emplace(ne);
			gg[ne].emplace_back(now);
		}
	}

	int now = s;
	cout << s;
	while(now != g) {
		sort(all(gg[now]));
		now = gg[now][0];
		cout << ' ' << now;
	}
	cout << endl;
}
0