数据结构与算法实验题 7.1 M 商人的求救

问题描述：

A 国正面临着一场残酷的战争，城市被支持不同领导的两股势力占据，作为一个商人,M先生并不太关心政治，但是他知道局势很严重，他希望你能救他出去。M 先生说：“为了安全起见，我们的路线最多只能包含一条连接两股不同势力城市的道路”。M 先生想知道最快多久能到达目的地。

数据输入：

第一行 N(2<=N<=600)，代表城市个数。第二行 M(0<=M<=10000)，代表道路条数。接 下 来 M 行 每 行 三 个 数 A,B,T 。 代 表 一 条 从 城 市 A 到 城 市 B 的 路 需 要 耗 时

T(1<=T<=1500)。接下来一行 N 个数，这些数只会是 1 或者 2，第 i 个数字代表第 i 个城市属于第几股势力。

为了简化问题，我们假设开始时 M 先生在城市 1，目的地是城市 2，城市 1 属于第 1 股势力，城市 2 属于第 2 股势力。道路是双向的。数据保证没有重边。

结果输出:

输出最少需要的时间。如果无法到达则输出-1。

输入示例：

2

1

1 2 100

1 2

3

3

1 2 100

1 3 40

2 3 50

1 2 1

5

5

3 1 200

5 3 150

2 5 160

4 3 170

4 2 170

1 2 2 2 1

输出示例：

100

90

540

“我们的路线最多只能包含一条连接两股不同势力城市的道路”故只能找到到到达某个城市后再到城市2最短路径。

代码12/17上传

---------------

先找出城市1到势力1所有节点的最短路径，城市2到势力2所有点的最短路径。

然后枚举从1到某个城市，再从这个城市到2的最短路。

#include<cstdio>

const int MAXN=600+5;

const int INF=999999;

int force[MAXN];

int map[MAXN][MAXN];

int dis[3][MAXN],n;

void Dijkstra(int kind)

{

	int cur=kind;

	bool vis[MAXN]={0};

	vis[cur]=true;

	dis[kind][cur]=0;

	int i,j;

	for(i=1;i<=n;i++)

	{

		int mini=INF;

		for(j=1;j<=n;j++)

			if(map[cur][j]!=INF && force[j]==kind && map[cur][j] + dis[kind][cur] < dis[kind][j] )

				dis[kind][j]=map[cur][j] + dis[kind][cur];

		for(j=1;j<=n;j++)

			if(!vis[j] && dis[kind][j] < mini)

				mini=dis[kind][cur=j];

		vis[cur]=true;

	}

}

int main()

{

	int i,j;

	scanf("%d",&n);

	for(i=1;i<=n;i++)

		for(j=1;j<=n;j++)

			map[i][j]=INF;

	int m;

	scanf("%d",&m);

	for(i=0;i<m;i++)

	{

		int a,b,t;

		scanf("%d%d%d",&a,&b,&t);

		map[a][b]=map[b][a]=t;

	}

	for(i=1;i<=n;i++)

	{

		scanf("%d",&force[i]);

		dis[1][i]=dis[2][i]=INF;

	}

	Dijkstra(1);

	Dijkstra(2);

	int ans=map[1][2],temp;

	for(j=1;j<=n;j++)

	{

		for(i=1;i<=n;i++)

		{

			if(force[i]!=force[j])

			{

				temp=map[i][j] + dis[1][j] + dis[2][i];

				if(temp<ans)

					ans=temp;

			}

		}

	}

	if(ans!=INF)

		printf("%d\n",ans);

	else

		printf("-1\n");

	return 0;

}