UVa 10850

UVa 10850"/>

UVa 10850

题目：有n个人，他们某些人每天固定的时刻会进行会面，从第一个人传递谣言，问所有人都知道最少需要多久。

分析：图论，最短路。之际利用bfs求解最短路即可。

            本题可以使用优先队列优化，这里数据较小，就没有用；

            每次更新最短路时注意，如果会面时间比现在的大则在同一天，否则在下一天（+100）。

说明：新的开始╮(╯▽╰)╭。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>using namespace std;int link[21][21][101];
int size[21][21];
int cost[21];int used[21];
int Q[21];
void bfs(int n)
{for (int i = 0; i < 21; ++ i) {cost[i] = 20002;used[i] = 0;}used[1] = 1;cost[1] = 0;Q[0] = 1;int move = 0,save = 1;while (move < save) {int now = Q[move ++];int min = 20002,New = 0;for (int i = 2; i <= n; ++ i) {if (used[i]) continue;for (int j = 0; j < size[now][i]; ++ j) {int costnew = cost[now]/100*100+link[now][i][j];if (costnew%100 < cost[now]%100)costnew = costnew+100;if (cost[i] > costnew)cost[i] = costnew;}if (min > cost[i]) {min = cost[i];New = i;}}if (New) {Q[save ++] = New;cost[New] = min;used[New] = 1;}}if (save == n)printf("%d\n",cost[Q[save-1]]);else printf("-1\n");
}int main()
{int T,n,k,a,b,m,t;while (~scanf("%d",&T))while (T --) {scanf("%d%d",&n,&k);memset(size, 0, sizeof(size));for (int i = 0; i < k; ++ i) {scanf("%d%d%d",&a,&b,&m);for (int j = 0; j < m; ++ j) {scanf("%d",&t);link[a][b][size[a][b] ++] = t;link[b][a][size[b][a] ++] = t;}}bfs(n);}return 0;
}