最短路 || Codeforces 938D Buy a Ticket

题意：从城市u到v（双向）要花w钱，每个城市看演唱会要花不同的门票钱，求每个城市的人要看一场演唱会花费最少多少（可以在这个城市看，也可以坐车到别的城市看，然后再坐车回来）

思路：本来以为是多源。。实际上是单源

考虑dij的松弛操作，是每次取队列里值最小的点u（队首），看它能拓展到的点v，如果经过u到v的代价比当前到v的代价低，那么就更新v

这里也同理，只不过代价是路程*2加上在v看演唱会的钱

嗯。。神奇的dij

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <cstring>

using namespace std;

typedef long long LL;

#define SZ 411000

int head[SZ],nxt[SZ],tot = ;

struct edge

{

    int t;

    LL d;

}l[SZ];

void build(int f,int t,LL d)

{

    l[++ tot] = (edge){t,d};

    nxt[tot] = head[f];

    head[f] = tot;

}

struct node

{

    int u;

    LL d;

};

bool vis[SZ];

LL dist[SZ];

priority_queue<node> q;

bool operator < (node a, node b) {return a.d > b.d; }

int main()

{

    int n, m, v, u;

    LL w;

    scanf("%d %d", &n, &m);

    for(int i = ; i < m; i++)

    {

        scanf("%d %d %lld", &v, &u, &w);

        build(v, u, w);

        build(u, v, w);

    }

    for(int i = ; i <= n; i++) scanf("%lld", &dist[i]), q.push((node){i, dist[i]} );

    while(q.size())

    {

        int u = q.top().u;

        q.pop();

        if(vis[u]) continue;

        vis[u] = ;

        for(int i = head[u]; i;i = nxt[i])

        {

            int v = l[i].t;

            if(dist[v] > dist[u] +  * l[i].d)

            {

                dist[v] = dist[u] +  * l[i].d;

                q.push((node){v, dist[v]});

            }

        }

    }

    for(int i = ; i <= n; i++)

    {

        if(i != ) printf(" ");

        printf("%lld", dist[i]);

    }

    printf("\n");

    return ;

}