Codeforces 229B【最短路+SPFA】

2018/04/18 10:49
阅读数 21

题目大意:我们要找一条从1到N的最短路。现在每个点都会在一些时间关闭通道,这些时间不能在这些点上。

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<string>  
#include<queue>
#include<vector>
#define MAX 100000+10
#define INF 0x3f3f3f3f
using namespace std;
int n, m;
int cnt;
int head[MAX];
vector<int> other[MAX];
int vis[MAX];
int dis[MAX];
struct E {
	int next, from, to, w;
}edge[1000000];

void add(int from, int to, int w) {
	edge[cnt].to = to;
	edge[cnt].w = w;
	edge[cnt].next = head[from];
	head[from] = cnt++;
	return;

}
int wait(int s, int time) {
	int t = 0;
	for (int i = 0; i < (int)other[s].size(); i++) {
		int tt = other[s][i];
		if (tt < time)
			continue;
		if (tt == time) {
			t++;
			time++;
		}
		else {
			break;
		}

	}
	return t;
}

void SPFA(int ss) {
	for (int i = 1; i <= n; i++) {
		dis[i] = INF;

	}
	vis[ss] = 1;
	dis[ss] = wait(ss, 0);
	queue<int> Q;
	Q.push(ss);
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		vis[u] = 0;
            //注意必须是在这里算出waittime,放在下一个循环里会WA
		int wait_time_for_u = dis[u] + wait(u, dis[u]);
		for (int i = head[u]; i != -1; i = edge[i].next) {
			int v = edge[i].to;
			int w = edge[i].w;
			int arrive_time = wait_time_for_u + w;
			if (dis[v] > arrive_time) {
				dis[v] = arrive_time;
				if (!vis[v]) {
					vis[v] = 1;
					Q.push(v);
				}
			}
		}

	}
}


int main(void) {
	while (~scanf("%d%d", &n, &m)) {
		memset(head, -1, sizeof(head));
		memset(vis, 0, sizeof(vis));
		memset(other, 0, sizeof(other));
		cnt = 0;
		for (int i = 1; i <= m; i++) {
			int a, b, d;
			scanf("%d%d%d", &a, &b, &d);
			add(a, b, d);
			add(b, a, d);
		}
		for (int i = 1; i <= n; i++) {
			int t, x;
			scanf("%d", &t);
			while (t--) {
				scanf("%d", &x);
				other[i].push_back(x);
			}
		}
		SPFA(1);
		if (dis[n] == INF) {
			printf("-1\n");
		}
		else {
			printf("%d\n", dis[n]);

		}

	}
	return 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部