結果

提出番号	1417
提出者	square1001
言語	C++
提出日時	2018-08-02 21:49:03
問題名	(49)最短経路問題
結果	AC
点数	100%

---

テストケース

ソースコード

#include <queue>
#include <vector>
#include <iostream>
using namespace std;
struct edge {
	int to, cost;
};
struct state {
	int pos; long long cost;
};
bool operator<(const state& s1, const state& s2) {
	return s1.cost > s2.cost;
}
int main() {
	int N, M, a, b, c;
	cin >> N >> M;
	vector<vector<edge> > G(N);
	for (int i = 0; i < M; ++i) {
		cin >> a >> b >> c; --a, --b;
		G[a].push_back(edge{ b, c });
		G[b].push_back(edge{ a, c });
	}
	vector<long long> dist(N, 1LL << 62); dist[0] = 0;
	priority_queue<state> que; que.push(state{ 0, 0 });
	while (!que.empty()) {
		state u = que.top(); que.pop();
		for (edge e : G[u.pos]) {
			if (dist[e.to] > dist[u.pos] + e.cost) {
				dist[e.to] = dist[u.pos] + e.cost;
				que.push(state{ e.to, dist[e.to] });
			}
		}
	}
	cout << (dist[N - 1] == (1LL << 62) ? -1 : dist[N - 1]) << '\n';
	return 0;
}