ソースコード
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "iomanip"
#include "cmath"
using namespace std;
const long long int MOD = 1000000007;
long long int N, M, K, H, W, L, R;
class CEdge {
public:
int to;
int cost;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
vector<vector<CEdge>>edge(N + 1);
vector<long long int>dis(N + 1, LLONG_MAX);
dis[1] = 0;
for (int i = 0; i < M; i++) {
cin >> L >> R >> K;
CEdge box;
box.to = R;
box.cost = K;
edge[L].push_back(box);
box.to = L;
edge[R].push_back(box);
}
priority_queue<pair<long long int, int>, vector<pair<long long int, int>>, greater<pair<long long int, int>>>PQ;
PQ.push({ 0,1 });
while (!PQ.empty()) {
int cn = PQ.top().second;
long long int c = PQ.top().first;
PQ.pop();
if (dis[cn] < c) {
continue;
}
for (auto i : edge[cn]) {
if (dis[i.to] > c + i.cost) {
dis[i.to] = c + i.cost;
PQ.push({ dis[i.to],i.to });
}
}
}
if (dis[N] == LLONG_MAX) {
cout << "-1\n";
return 0;
}
cout << dis[N] << endl;
return 0;
}