记录编号	584744	评测结果	AAAAAAAAAAA
题目名称	[GXOI/GZOI2019]旅行者	最终得分	100
用户昵称	宇战	是否通过	通过
代码语言	C++	运行时间	8.150 s
提交时间	2023-11-14 19:30:16	内存使用	34.82 MiB

    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 500010;
    int n, m, k, a[MAXN], dis[MAXN], pos[MAXN], ans;
    bool vis[MAXN];
    vector<int> cd[MAXN], w[MAXN];
    struct node {
    	int num, dis;
    	bool operator < (const node& x) const {
    		return  x.dis < dis;
    	}
    }st;
    priority_queue<node> q;
    int dijkstra(int x) {
    	memset(vis, 0, sizeof(vis));
    	memset(dis, 0x3f, sizeof(dis));
    	dis[x] = 0;
    	st.num = x;
    	st.dis = dis[x];
    	q.push(st);
    	while(!q.empty()) {
    		int u = q.top().num;
    		q.pop();
    		if(pos[u] && u != x) {
    			return dis[u];
    		}
    		if(vis[u]) {
    			continue;
    		}
    		vis[u] = 1;
    		for(int i = 0; i < cd[u].size(); i ++) {
    			int v = cd[u][i];
    			if(!vis[v] && dis[v] > dis[u] + w[u][i]) {
    				dis[v] = dis[u] + w[u][i];
    				st.num = v;
    				st.dis = dis[v];
    				q.push(st);
    			}
    		}
    	}
    	return 1e15;
    }
    int main() {
    	freopen("WAW.in", "r", stdin);
    	freopen("WAW.out", "w", stdout);
    	int t;
    	cin >> t;
    	while(t --) {
    	memset(pos, 0, sizeof(pos));
    	ans = 1e15;
    	cin >> n >> m >> k;
    	for(int i = 1; i <= n; i ++) {
    		cd[i].clear();
    		w[i].clear();
    	}
    	for(int i = 1; i <= m; i ++) {
    		int x, y, z;
    		cin >> x >> y >> z;
    		cd[x].push_back(y);
    		w[x].push_back(z);
    	}
    	for(int i = 1; i <= k; i ++) {
    		int x;
    		cin >> x;
    		pos[x] = 1;
    	}
    	for(int i = 1; i <= n; i ++) {
    		if(pos[i]) {
    			ans = min(ans, dijkstra(i));
    		}
    	}
    	cout << ans << endl;
    	}
    	return 0;
    }