最短路模板

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXM = 200005;
struct edge{
    int to, next;
    long long w;
}e[MAXM];
int cnt, head[MAXM];
int n, m, s;
priority_queue< pair<int, int> > q;
int d[MAXM], vis[MAXM];

void add(int u, int v, long long val)
{
    e[++cnt].to = v;
    e[cnt].next = head[u];
    e[cnt].w = val;
    head[u] = cnt;
}

int main()
{
    cin >> n >> m >> s;
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    
    for(int i = 1; i <= n; i++)
      d[i] = 2147483647;
    int p = s;
    q.push(make_pair(0, p));
    d[p] = 0;
    while(!q.empty())
    {
        int x = q.top().second; 
        q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = head[x]; i; i = e[i].next)
        {
            if( d[e[i].to] > (d[x] + e[i].w))
            {
                d[e[i].to] = (d[x] + e[i].w);
                q.push(make_pair(-d[e[i].to], e[i].to));    
            }
        }
    }
    for(int i = 1; i <= n; i++)
        cout << d[i] << " ";
    return 0;
}