首页 > 代码库 > SGU 226.Colored graph

SGU 226.Colored graph

2024-07-11 08:33:26   219人阅读

时间限制：0.25s

空间限制：4M

题意：

       给出一个n个节点，m条边的图，每条边都有标记了编号为1,2,3三种颜色之一，现在求从1号节点到n号节点的一条最短路径的长度，要求该路径中相邻的边没有相同的颜色。

 

 

 

 

Solution：

              有限制条件的SPFA，要注意有时要形成环来改变路径颜色，才能到达目标点。

 

 

参考代码

#include <iostream>#include <cstring>#include <cstdio>#include <queue>#define INF 300using namespace std;struct node {	int v, ne, c;} edge[INF * INF];queue<int> ql;int head[INF], pd[INF];int dis[INF][4], cnt,n,m;void added (int u, int v, int c) {	edge[++cnt].v = v, edge[cnt].c = c;	edge[cnt].ne = head[u];	head[u] = cnt;}void spfa() {	while (!ql.empty() ) {		int x = ql.front();		pd[x] = 0,ql.pop();		for (int i = head[x]; i != 0; i = edge[i].ne) {			int j = edge[i].v, color = edge[i].c;			for (int k = 1; k <= 3; k++) {				if (k == color || dis[x][k] == -1) continue;				if (dis[j][color] == -1 || dis[j][color] > dis[x][k] + 1) {					dis[j][color] = dis[x][k] + 1;					if (!pd[j])						pd[j] = 1, ql.push (j);				}			}		}	}}int main() {	int  x, y, c;	scanf ("%d %d", &n, &m);	memset (dis, -1, sizeof dis);	for (int i = 1; i <= m; i++) {		scanf ("%d%d%d", &x, &y, &c);		added (x, y, c);	}	ql.push (1); pd[1] = 1;	dis[1][1] = dis[1][2] = dis[1][3] = 0;	spfa();	int ans = INF<<12;	for (int i = 1; i <= 3; i++)		if (dis[n][i] != -1)			ans = min (ans, dis[n][i]);	if (ans != INF<<12) printf ("%d", ans);	else		puts ("-1");	return 0;}

　　

 

 


联系
我们