[ZJ] a833: 3、沙漠旅行

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
struct P{
    int x,y;
    friend bool operator < (P a,P b){
        return a.y>b.y;
    }
}in,out;
vector<P> s[500005];
priority_queue<P> que;
int v[500005]={0},d[500005];
int main(){
    int n,m,i,x,y,z;
    scanf("%d%d",&n,&m);
    for(i=2;i<=n;i++)
        d[i]=1e8;
    for(i=0;i<m;i++){
        scanf("%d%d%d",&x,&y,&z);
        s[x].push_back((P){y,z});
    }
    d[1]=0;
    for(i=0;i<s[1].size();i++)
        que.push(s[1][i]);
    while(que.size()){
        out=que.top();
        que.pop();
        if(v[out.x]) continue;
        v[out.x]=1,d[out.x]=out.y;
        for(i=0;i<s[out.x].size();i++){
            in=out;
            in.x=s[out.x][i].x;
            if(v[in.x]) continue;
            in.y+=s[out.x][i].y;
            que.push(in);
        }
    }
    printf("%d\n",d[n]);
}