虽然草儿是个路痴(就是在杭电待了一年多,居然还会在校园里迷路的人,汗~),但是草儿仍然很喜欢旅行,因为在旅途中 会遇见很多人(白马王子,^0^),很多事,还能丰富自己的阅历,还可以看美丽的风景……草儿想去很多地方,她想要去东京铁塔看夜景,去威尼斯看电影,去阳明山上看海芋,去纽约纯粹看雪景,去巴黎喝咖啡写信,去北京探望孟姜女……眼看寒假就快到了,这么一大段时间,可不能浪费啊,一定要给自己好好的放个假,可是也不能荒废了训练啊,所以草儿决定在要在最短的时间去一个自己想去的地方!因为草儿的家在一个小镇上,没有火车经过,所以她只能去邻近的城市坐火车(好可怜啊~)。
Input
输入数据有多组,每组的第一行是三个整数T,S和D,表示有T条路,和草儿家相邻的城市的有S个,草儿想去的地方有D个;
接着有T行,每行有三个整数a,b,time,表示a,b城市之间的车程是time小时;(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数,表示和草儿家相连的城市;
接着的第T+2行有D个数,表示草儿想去地方。
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
多源起点到多源终点的距离
把草儿的家记作0点 , 他离最近的城市的距离为0.这样也就变成了单源点到其他点之间的最短距离。
二刷记一下坑点,emm。。。。dis[]数组从0 开始所以循环是0 ~ s-1
松弛操作那儿也写错了 , vector用的不熟 , 唉
vector存地图代码:
#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;
#include <vector>
#define INF 0x3f3f3f3f
const int maxn = 1009;
int vis[maxn] , dis[maxn] , want[maxn] , book[maxn];
int n , m , u ,minn ;
struct node
{
int to ;
int cost;
node(int _to , int _cost):to(_to) , cost(_cost){}
};
int max(int a , int b)
{
if(a > b)
{
return a;
}
else
{
return b;
}
}
vector<node>V[maxn];
void Dijkstra(int s)
{
for(int i = 0 ; i <= s -1 ; i++)
{
minn = INF;
for(int j = 1 ; j <= s ; j++)
{
if(vis[j] == 0 && dis[j] < minn)
{
minn = dis[j];
u = j;
}
}
vis[u] = 1;
for(int k = 0 ; k < V[u].size() ; k++)
{
int v = V[u][k].to;
int w = V[u][k].cost;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
}
}
}
}
int main()
{
int T , S , D;
while(~scanf("%d %d %d" , &T , &S , &D))
{
int ans = 0;
int u , v , cost , w ,small = INF ;
memset(vis , 0 , sizeof(vis));
memset(book , 0 , sizeof(book));
for(int i = 0 ; i < maxn ; i++) V[i].clear();
while(T--)
{
scanf("%d %d %d" , &u , &v , &cost);
ans = max(ans , max(u , v));
V[u].push_back(node(v , cost));
V[v].push_back(node(u , cost));
}
while(S--)
{
scanf("%d" ,&w);
V[0].push_back(node(w , 0));
V[w].push_back(node(0 , 0));
}
for(int i = 0 ; i < D ; i++)
{
scanf("%d" , &want[i]);
}
memset(dis , INF , sizeof(dis));
vis[0] = 1;
for(int i = 0 ; i < V[0].size() ; i++)
{
dis[V[0][i].to] = V[0][i].cost;
}
dis[0] = 0;
Dijkstra(ans);
for(int i = 0; i < D ; i++)
{
if(dis[want[i]] < small)
{
small = dis[want[i]];
}
}
printf("%d\n" , small);
}
return 0;
}
加一份用邻接矩阵写的代码:
#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 1009;
int vis[maxn] , data[maxn][maxn] , dis[maxn] , want[maxn];
int n ,m , minn , u;
void Dijkstra(int s)
{
for(int i = 0 ; i <= s-1 ; i++)
{
minn = INF;
for(int j = 0 ; j <= s ; j++)
{
if(vis[j] == 0 && dis[j] < minn)
{
minn = dis[j];
u = j;
}
}
vis[u] = 1;
for(int k = 0 ; k <= s ; k++)
{
if(dis[k] > dis[u] + data[u][k])
{
dis[k] = dis[u] + data[u][k];
}
}
}
}
int main()
{
int T , S , D , s , ans;
int a , b ,c , d ,e;
while(scanf("%d %d %d" , &T , &S , &D)!=EOF)
{
memset(vis , 0 , sizeof(vis));
memset(dis , INF , sizeof(dis));
memset(data,INF,sizeof(data));
while(T--)
{
scanf("%d %d %d" , &a , &b , &c);
s = max(s,max(a,b));
if(data[a][b] > c)
{
data[a][b] = c;
data[b][a] = c;
}
}
while(S--)
{
scanf("%d" , &d);
data[0][d] = 0;
}
for(int i = 0 ; i < D ; i++)
{
scanf("%d" , &want[i]);
}
vis[0] = 1;
for(int i = 0 ; i <= s ; i++)
{
dis[i] = data[0][i];
}
dis[0] = 0;
Dijkstra(s);
ans = INF;
for(int i = 0 ; i < D ; i++)
{
if(ans > dis[want[i]])
{
ans = dis[want[i]];
}
}
printf("%d\n" , ans);
}
return 0;
}