多起点多终点最短路 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;
}