多起点多终点最短路 T3 有一天,琪琪想乘坐公交车去拜访她的一位朋友。
由于琪琪非常容易晕车,所以她想尽快到达朋友家。
现在给定你一张城市交通路线图,上面包含城市的公交站台以及公交线路的具体分布。
已知城市中共包含 个车站(编号~)以及 条公交线路。
每条公交线路都是 单向的,从一个车站出发直接到达另一个车站,两个车站之间可能存在多条公交线路。
琪琪的朋友住在 号车站附近。
琪琪可以在任何车站选择换乘其它公共汽车。
请找出琪琪到达她的朋友家(附近的公交车站)需要花费的最少时间。
输入格式
输入包含多组测试数据。
每组测试数据第一行包含三个整数 ,分别表示车站数量,公交线路数量以及朋友家附近车站的编号。
接下来 行,每行包含三个整数 ,表示存在一条线路从车站 到达车站 ,用时为 。
接下来一行,包含一个整数 ,表示琪琪家附近共有 个车站,她可以在这 个车站中选择一个车站作为始发站。
再一行,包含 个整数,表示琪琪家附近的 个车站的编号。
输出格式
每个测试数据输出一个整数作为结果,表示所需花费的最少时间。
如果无法达到朋友家的车站,则输出 -1。
每个结果占一行。
数据范围
,
,
,
输入样例:
5 8 5
1 2 2
1 5 3
1 3 4
2 4 7
2 5 6
2 3 5
3 5 1
4 5 1
2
2 3
4 3 4
1 2 3
1 3 4
2 3 2
1
1
输出样例:
1
-1
思路
通过建一个虚拟源点, 和各个起点连一条权值为0的边, 然后对所有点做最短路即可。
代码
#define S second
#define F first
#define pb push_back
#define pf push_front
#define lson l, mid, u << 1
#define rson mid + 1, r, u << 1 | 1
#define MID l + r >> 1
#define mem(x, n) memset(x, n, sizeof x)
#define setPrec(n) cout << fixed << setpricision(n)
// #define debug
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e3 + 10, M = 2e4 + 10, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
int h[N], e[M], w[M], ne[M], idx;
int n, m, s;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dist[N];
bool st[N];
void solve()
{
mem(dist, 0x3f);
priority_queue<PII, vector<PII>, greater<PII>> q;
mem(st, 0);
q.push({0, 0});
dist[0] = 0;
while (q.size())
{
auto t = q.top();
q.pop();
int ver = t.S, d = t.F;
if (st[ver])
continue;
st[ver] = true;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
dist[j] = min(dist[j], d + w[i]);
if (!st[j])
q.push({dist[j], j});
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> n >> m >> s, n)
{
mem(h, -1);
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int w;
cin >> w;
while (w--)
{
int t;
cin >> t;
add(0, t, 0);
}
solve();
if (dist[s] == INF)
cout << -1 << endl;
else
cout << dist[s] << endl;
}
return 0;
}