競プロC++ dijkstra法
そういった理由から別の方には向かないかもしれません
関連タイピング
-
プレイ回数1464英語60秒
-
プレイ回数2.1万英字60秒
-
プレイ回数20英字60秒
-
プレイ回数601英語長文300秒
-
プレイ回数1959長文297打
-
プレイ回数3596英字30秒
-
プレイ回数1214英語長文1638打
-
プレイ回数959英字444打
問題文
(#include <iostream>)
#include <iostream>
(#include <vector>)
#include <vector>
(#include <queue>)
#include <queue>
(using namespace std;)
using namespace std;
(using ll = long long;)
using ll = long long;
(struct Edge{)
struct Edge{
(int to;)
int to;
(ll weight;)
ll weight;
(Edge(int t, ll w): to(t), weight(w) {})
Edge(int t, ll w): to(t), weight(w) {}
(int main(){)
int main(){
(int n, m;)
int n, m;
(cin >> n >> m;)
cin >> n >> m;
(for(int i = 0; i < m; ++i){)
for(int i = 0; i < m; ++i){
(int a, b;)
int a, b;
(ll c;)
ll c;
(cin >> a >> b >> c;)
cin >> a >> b >> c;
(--a;)
--a;
(--b;)
--b;
(g[a].push_back(Edge(b, c));)
g[a].push_back(Edge(b, c));
(g[b].push_back(Edge(a, c));)
g[b].push_back(Edge(a, c));
(priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;)
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
(pq.push({0, 0});)
pq.push({0, 0});
(const ll INF = 1ll << 60;)
const ll INF = 1ll << 60;
(vector<ll> dist(n, INF);)
vector<ll> dist(n, INF);
(dist[0] = 0;)
dist[0] = 0;
(while(!pq.empty()){)
while(!pq.empty()){
(auto [d, v] = pq.top();)
auto [d, v] = pq.top();
(pq.pop();)
pq.pop();
(if(dist[v] != d) continue;)
if(dist[v] != d) continue;
(for(auto ne: g[v]){)
for(auto ne: g[v]){
(int nv = ne.to;)
int nv = ne.to;
(if(dist[nv] > dist[v] + ne.weight){)
if(dist[nv] > dist[v] + ne.weight){
(dist[nv] = dist[v] + ne.weight;)
dist[nv] = dist[v] + ne.weight;
(pq.push({dist[nv], nv});)
pq.push({dist[nv], nv});
(ll res = dist.back();)
ll res = dist.back();
(if(res == INF) res = -1;)
if(res == INF) res = -1;
(cout << res << endl;)
cout << res << endl;
(return 0;)
return 0;