Submission #76528568

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18;
const int MAXM = 1048576;
int n,m;
int h[MAXM],cnt = 0;
ll d[MAXM];
bool vis[MAXM];

struct Edge{
    int to, nxt;
    ll dis;
}e[MAXM];

void add(int u,int v,ll w){
    e[++cnt] = {v,h[u],w};
    h[u] = cnt;
    return ;
}

struct Node{
    ll dis;
    int pos;
    bool operator<(const Node &x)const{
        return x.dis<dis;
    }
};

void dij(int s){
    for(int i=1;i<=n;i++){
    	d[i] = INF;
	}
    d[s] = 0;
    priority_queue<Node> pq;
    pq.push({0, s});
    while(!pq.empty()){
        Node tmp = pq.top();
		pq.pop();
        int u = tmp.pos;
        if(vis[u]){
        	continue;
		}
        vis[u] = 1;
        for(int i=h[u];i!=0;i=e[i].nxt){
            int v = e[i].to;
            ll w = e[i].dis;
            if(d[v] > d[u]+w){
                d[v] = d[u] + w;
                pq.push({d[v],v});
            }
        }
    }
    return ;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;
		ll w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dij(1);
    if(d[n] == INF){
    	cout<<-1<<endl;
	}
    else{
    	cout<<d[n]<<endl;
	}
    return 0;
}

Submission Info

Judge Result