Dijkstra模板

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+2;
const int INF =1e9+7;
int dis[maxn];bool vis[maxn];// ò???ê??àà?êy×é￡?ò???ê?±ê??êy×é 
// ×￠òa ó??è?óáD??è?ê1ó? < ±è?? ???ò??è?ê?′óμ??μ?ú?°???￡óéóúdijkstraê?ê1ó?
// ì???×?D??μ￡??ùò??ò??òa?????? < ????·?￡????òè?D?μ??ú?°??￡?ê?·′μ?. 
struct Node{
    int v,cost;
    bool operator < (const Node &rhs) const{
        return cost>rhs.cost;
    }
};
vector<Node> G[maxn];
int main(){
    int n,m,s;cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back((Node){ v,w});    
    }
    for(int i=0;i<=n;i++){
        dis[i]=INF;vis[i]=false;
    } //±eíüá?3?ê??ˉ 
    dis[s]=0;
    priority_queue<Node> q;
    q.push((Node){ s,0});
    while(!q.empty()){
        int x=q.top().v; q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(int i=0;i<G[x].size();i++){
            int to=G[x][i].v;int w=G[x][i].cost;
            if(dis[to]>dis[x]+w){
                dis[to]=dis[x]+w;
                q.push((Node){ to,dis[to]});
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
return 0;}