Til the Cows Come Home

题意：

找出从1点 和 N点的最短路

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#define pi acos(-1.0)
#define eps 1e-9
const int mxn = 1e6+7 ;
const int INF = 0x3f3f3f3f ;
using namespace std;
typedef long long ll;
template <class T>
void rd(T &x){
    x=0;T f=1;char c=getchar();
    while(!isdigit(c)) {if(c=='-') f = -1 ; c = getchar();}
    while(isdigit(c)) {x = (x<<1) + (x<<3) + (c^48);c = getchar();}
    x*=f;
}
int p,t,n,m,k,si,ans,cnt,head[mxn],dis[mxn];
bool vis[mxn] ;
struct ${
    int to , nx , w ;
}e[mxn];
void add(int u,int v,int w)
{
    e[cnt].to = v ;
    e[cnt].w = w ;
    e[cnt].nx = head[u] ;
    head[u] = cnt++;
}
void dij()
{
    priority_queue<pair<int,int> , vector<pair<int,int> > , greater<pair<int,int> > > q;
    for(int i=1;i<=m;i++) dis[i] = INF , vis[i] = false ;
    q.push({0,m}); dis[m] = 0 ;
    while(!q.empty()){
        int w = q.top().first , u = q.top().second ; q.pop() ;
        if(vis[u]) continue ;
        vis[u] = true ;
        for(int i=head[u];~i;i=e[i].nx){
            int v = e[i].to , w = e[i].w ;
            if(!vis[v] && dis[v]>dis[u]+w)
                dis[v] = dis[u] + w , q.push({dis[v],v});
        }
    }
    printf("%d\n",dis[1]);
}
int main()
{
    rd(n) , rd(m) ; cnt = 0 ;
    memset(head,-1,sizeof(head));
    for(int i=1,u,v,w;i<=n;i++){
        rd(u) , rd(v) , rd(w) ;
        add(u,v,w);
        add(v,u,w);
    }
    dij();
}