Submission #1794947

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
typedef pair<int, int> pii;
const int INF = 1e9;
int ans = INF;
int N, M;
vector<pii> node[100005];
vector<int> minCost;
void dijkstra() {
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for (int i = 0; i < N; ++i) {
		fill(minCost.begin(), minCost.end(), INF);
		minCost[i] = 0;
		pq.push(pii(0, i));
		while (!pq.empty()) {
			pii now = pq.top(); pq.pop();
			int cost = now.first;
			int id = now.second;
			for (int j = 0; j < node[id].size(); ++j) {
				int nCost = node[id][j].first;
				int nId = node[id][j].second;
				if (cost + nCost < minCost[nId]) {
					minCost[nId] = cost + nCost;
					pq.push(pii(minCost[nId], nId));
				}
			}
		}
		sort(minCost.begin(), minCost.end(), greater<int>());
		ans = min(ans, minCost[0]);
	}
}
int main(void) {
	cin >> N >> M;
	minCost.resize(N);
	for (int i = 0; i < M; ++i) {
		int a, b, c; cin >> a >> b >> c;
		node[a - 1].push_back(pii(c, b - 1));
		node[b - 1].push_back(pii(c, a - 1));
	}
	dijkstra();
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result