csust T1097 “是时候表演真正的技术了” 题解（虚点跑最短路）

题目链接

题目大意

给你n个点m条路，以及k个宝藏点，q次查询要你求出距离这个点最近的宝藏点的距离

题目思路

一个套路题，建立虚点与k个点连一个权值为0的边，跑最短路即可

注意边多了4000条

代码

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
#define fi first
#define se second
//#define int long long
#define debug printf(" I am here
");
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,int> pii;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=3e5+5+4000,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-10;
int n,m,k;
ll dis[maxn];
int head[maxn],cnt;
struct edge{
    int to,next,w;
}e[maxn<<1];
void add(int u,int v,int w){
    e[++cnt]={v,head[u],w};
    head[u]=cnt;
}
void dij(int x){
	priority_queue<pii,vector<pii>,greater<pii> > que;
	memset(dis,0x3f,sizeof(dis));
	dis[x]=0;
	que.push({0,x});
	while(!que.empty()){
		int len=que.top().first;
		int pos=que.top().second;
		que.pop();
		if(len<=dis[pos]){
			for(int i=head[pos];i;i=e[i].next){
				if(dis[e[i].to]>dis[pos]+e[i].w){
					dis[e[i].to]=dis[pos]+e[i].w;
					que.push({dis[e[i].to],e[i].to});//一定注意是len为fi
				}
			}
		}
	}
}
signed main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1,x;i<=k;i++){
        scanf("%d",&x);
        add(x,n+1,0),add(n+1,x,0);
    }
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    }
    dij(n+1);
    int _; scanf("%d",&_);
    while(_--){
        int x; scanf("%d",&x);
        printf("%lld
",dis[x]);
    }
    return 0;
}