Handy的生产线题解

题面翻译

以 $1$ 为目标节点，求各点到 $1$ 节点的最短路。表面上这是一个多元最短路的问题，因为每次询问的起点不一。但是观察到每次的终点相同，所以如果将所有的边反向连接来建图，就变成了唯一起点，多个终点的单元最短路问题，由于题目中没有负环，所以直接考虑使用 $dijkstra$ 算法。值得注意的是，单个边权高达 $10^9$ ，所以需要使用 $long$ $long$ 来存边权。

$ps:$ 我为mc举大旗，喜欢玩mc的可以来找我！！！

标准程序

#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 200005
using namespace std;

int cnt;
int first[MAXN];
long long dis[MAXN];
bool judge[MAXN];

struct Edge {
	int to, next;
	long long value;
}edge[MAXM];

void edges(int from, int to, long long value){
	edge[++cnt].to = to;
	edge[cnt].value = value;
	edge[cnt].next = first[from];
	first[from] = cnt;
}

struct HeapNode {
	long long dis; int u;
	bool operator < (const HeapNode &rhs) const{
		return dis > rhs.dis;
	}
};

void dijkstra(int s){
	priority_queue <HeapNode> q;
	dis[s] = 0;
	//memset(judge, false, sizeof(judge));
	q.push((HeapNode){0, s});
	while(!q.empty()){
		HeapNode point = q.top();
		q.pop();
		if(judge[point.u]) continue;
		judge[point.u] = true;
		for(int i = first[point.u]; i; i = edge[i].next){
			int to = edge[i].to;
			if(dis[to] > dis[point.u] + edge[i].value){
				dis[to] = dis[point.u] + edge[i].value;
				q.push((HeapNode){dis[to], to});
			}
		}
	}
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        cnt = 0;
        for(int i = 0; i < MAXN ;i++){
            first[i] = 0;
            dis[i] = 0;
            judge[i] = false;
        }
        for(int i = 0; i < MAXM; i++) edge[i] = (Edge){0,0,0};
        int n, m, q;
        scanf("%d%d%d", &n, &m ,&q);
        for(int i = 1; i <= m; i++){
            int from, to;
            long long value;
            scanf("%d%d%lld", &from, &to, &value);
            edges(to, from, value);
            //edges(to, from, value);
        }
        for(int i = 1; i <= n; i++) dis[i] = 2147483647123456;
        dijkstra(1);
        for(int i = 1; i <= q; i++){
            int s;
            scanf("%d", &s);
            printf("%lld\n", dis[s]);
        }
    }
	return 0;
}