问题描述：
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
100
3
3
1 2 100
1 3 40
2 3 50
1 2 1
90
5
5
3 1 200
5 3 150
2 5 160
4 3 170
4 2 170
1 2 2 2 1
540
并查集+dijstra算法
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define inf 0xffffff
int g[][];
struct ufs
{
int parent[];
}u;
int find(int e)
{
if(e!=u.parent[e])
u.parent[e]=find(u.parent[e]);
return u.parent[e];
}
void funion(int i,int j)
{
u.parent[i]=j;
}
void dijstra(int n)
{
int lowcost[],used[],min,i,j,k;
memset(used,,sizeof(used));
for(i=;i<=n;i++)
lowcost[i]=g[i][];
used[]=;
for(i=;i<n;i++)
{
j=;
min=inf;
for(k=;k<=n;k++)
{
if(lowcost[k]<min&&!used[k])
min=lowcost[k],
j=k;
}
used[j]=;
for(k=;k<=n;k++)
{
int t1=find(k),t2=find(j),t3=find();
if(t1==t3&&t2!=t1)//横跨两股势力
{
}
else
{
if(g[k][j]+lowcost[j]<lowcost[k]&&!used[k])
lowcost[k]=g[k][]=g[][k]=g[k][j]+lowcost[j];
}
}
}
}
int main()
{
int n,m,i,a,b,j,t;
scanf("%d %d",&n,&m);
for(i=;i<=n;i++)
u.parent[i]=i;
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
g[i][j]=inf;
g[i][i]=;
}
for(i=;i<=m;i++)
{
scanf("%d %d %d",&a,&b,&t);
g[a][b]=g[b][a]=t;
}
for(i=;i<=n;i++)
{
scanf("%d",&a);
if(a==)
funion(i,);
else if(a==)
funion(i,);
}
dijstra(n);
if(g[][]==inf)
printf("-1\n");
else
printf("%d\n",g[][]); return ;
}
| 5910 | 031202110 | M.cpp | AC|AC|AC|AC|AC|AC|AC|AC|AC|AC| | 77MS | 1660KB |