Time Limit: 1000MS Memory Limit: 32768KB 64bit IO Format: %I64d & %I64u

Description

Input

Output

Sample Input

6 2 3

1 3 5

1 4 7

2 8 12

3 8 4

4 9 12

9 10 2

1 2

8 9 10

Sample Output

9

Source

RPG专场练习赛

AC代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int t, s, d, k;
int dis[1010];
bool vis[1010];
int goal[1010];
struct edge
{
int v, w, next;
}e[5010];
queue <int> q;
void adde(int u, int v, int w)
{
e[k].v = v;
e[k].w = w;
}
void input()
{
int u, v, w;
for (int i = 1; i <= t; i++)
{
scanf("%d%d%d", &u, &v, &w);
}
for (int i = 0; i < s; i++)
{
scanf("%d", &v);
}
for (int i = 0; i < d; i++)
scanf("%d", &goal[i]);
}
void init()
{
k = 1;
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[0] = 0;
while (!q.empty())
q.pop();
}
void spfa()
{
q.push(0);
vis[0] = 1;
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = head[u]; i != -1; i = e[i].next)
{
int v = e[i].v;
if (dis[v] > dis[u] + e[i].w)
{
dis[v] = dis[u] + e[i].w;
if (!vis[v])
{
vis[v] = 1;
q.push(v);
}
}
}
}
}
void solve()
{
int ans = 0x3f3f3f3f;
spfa();
for (int i = 0; i < d; i++)
ans = min(ans, dis[goal[i]]);
printf("%d\n", ans);
}
int main()
{
while (scanf("%d%d%d", &t, &s, &d) == 3)
{
init();
input();
solve();
}
return 0;
}

Vhjbcf