首页 > 代码库 > poj 3767 I Wanna Go Home

poj 3767 I Wanna Go Home

2024-07-06 14:30:00   231人阅读



Description

The country is facing a terrible civil war----cities in the country are divided into two parts supporting different leaders. As a merchant, Mr. M does not pay attention to politics but he actually knows the severe situation, and your task is to help him reach home as soon as possible.

"For the sake of safety,", said Mr.M, "your route should contain at most 1 road which connects two cities of different camp."

Would you please tell Mr. M at least how long will it take to reach his sweet home?

Input

The input contains multiple test cases.

The first line of each case is an integer N (2<=N<=600), representing the number of cities in the country.

The second line contains one integer M (0<=M<=10000), which is the number of roads.

The following M lines are the information of the roads. Each line contains three integers A, B and T, which means the road between city A and city B will cost time T. T is in the range of [1,500].

Next part contains N integers, which are either 1 or 2. The i-th integer shows the supporting leader of city i.

To simplify the problem, we assume that Mr. M starts from city 1 and his target is city 2. City 1 always supports leader 1 while city 2 is at the same side of leader 2.

Note that all roads are bidirectional and there is at most 1 road between two cities.

Input is ended with a case of N=0.

Output

For each test case, output one integer representing the minimum time to reach home.

If it is impossible to reach home according to Mr. M‘s demands, output -1 instead.

Sample Input

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
0

Sample Output

100
90
540
题意：某个地区发生争执，所有的城市分为了两个阵营，一部分城市归属为1，一部分城市归属为2.Mr.M居住在城市1，现在他想回到故乡城市2（城市1和城市2归属于不同的阵营），但是途中只能经过连接两个阵营的城市道路中的一条，让你求出最短的路径。
思路：既然氛围两个阵营，那么就用两个数组将两个阵营的城市分别记录下来，然后再按阵营来分，将两个阵营内部的最短路求出来，然后在枚举最短路就行了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define INF 100000000
using namespace std;
int root[602],vis[602];         //root用来记录阵营标志
int dist1[610],dist2[610];      //分别记录两个阵营内部的最短路
int map[602][602];
int n,m;
void dijk(int s,int dist[])    //dijstra求取最短路
{
    for(int i=1; i<=n; i++)
        dist[i]=map[s][i];
    vis[s]=1;
    for(int i=1; i<=n; i++)
    {
        int mi=INF,k=0;
        for(int j=1; j<=n; j++)
            if(!vis[j]&&mi>dist[j]&&root[j]==root[s])
            {
                mi=dist[j];
                k=j;
            }
        if(k==0) break;
        vis[k]=1;
        for(int j=1; j<=n; j++)
            if(!vis[j]&&(root[j]==root[s])&&dist[j]>dist[k]+map[k][j])
                dist[j]=dist[k]+map[k][j];
    }
}
void init()                    //初始化函数
{
    for(int i=0; i<=n; i++)
        for(int j=0; j<=i; j++)
            if(i!=j) map[i][j]=map[j][i]=INF;
            else map[i][j]=0;
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        init();
        scanf("%d",&m);
        int x,y,z;
        int l[602],r[602],len=0,ren=0;           //l和r用来记录两个阵营的城市，len是1阵营里面城市的个数，ren是2阵营城市的个数
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            if(map[x][y]>z||map[x][y]==-1) map[x][y]=map[y][x]=z;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&root[i]);
            map[i][i]=0;
            if(root[i]==1) l[len++]=i;
            else r[ren++]=i;
            vis[i]=0;
        }
        dijk(1,dist1);          //用来求出两个阵营内部的最短路
        dijk(2,dist2);
        int ans=-1;
        for(int i=0;i<len;i++)       //暴力枚举最短路
        {
            for(int j=0;j<ren;j++)
            if(ans==-1||ans>dist1[l[i]]+dist2[r[j]]+map[l[i]][r[j]])
                    ans=dist1[l[i]]+dist2[r[j]]+map[l[i]][r[j]];
        }
        if(ans==-1||ans>5000000) cout<<-1<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}
































        

            
                
                  
                
                

                    联系

                    我们