学步园

题意：给你N个点M条边。

接下来M行s,e,l,分别表示s-e的路程是l（无向图）

接下来输入N个数，分别表示第i个城市支持那个leader.（1和2）

问：一个人从城市1出发到城市2，到达的过程中只能有一次跨越两个支持不同leader的城市，输出最短路程，或者-1；

思路：

一开始想在SPFA里面加个限制条件，来记录城市跨越的情况，但是貌似不好写。

就DIY了一种想法。

进行2次SPFA；

第一次：

从城市1出发，将城市1 到达 第一次出现支持不同leader的城市 的dis[]记录下来。

如样例3：

5
5
3 1 200
5 3 150
2 5 160
4 3 170
4 2 170
1 2 2 2 1

此时记录的dis[]值为：

dis[1]=0;

dis[2]=inf;

dis[3]=200;

dis[4]=inf;

dis[5]=inf;

第二次：

从城市2出发，将城市2到所有 相同阵营的城市(或者1，当然到达1之前必须没经过阵营变化)  的路程记为dis2[]。

同样是上面的样例：

dis1[1]=540;

dis1[2]=0;

dis1[3]=340;

dis1[4]=170;

dis1[5]=inf;

最后再枚举dis[]+dis1[]的最小值即可。若没有则输出-1；

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2005
#define inf 1<<28
using namespace std;

int n,m;
struct kdq
{
    int e,w;
};
vector<kdq>g[Max];
int agree[Max];
bool visit[Max];
void spfa(int s,int *dis)
{
    int i,j;
    for(i=1; i<=n; i++)
        dis[i]=inf;
    dis[s]=0;
    visit[s]=1;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int temp=q.front();
        q.pop();
        visit[temp]=0;
        for(i=0; i<g[temp].size(); i++)
        {
            int v=g[temp][i].e;
            int w=g[temp][i].w;
            if(agree[s]!=agree[v]&&s==2)//当起点为2时，那么当阵营发生变化，并且不是变化到城市1，那么此点不处理，continue;
            {
                if(v!=1)
                continue;
            }
            if(agree[s]!=agree[v]&&s==1)//更新起点1时，只经过一次阵营变化的dis[]值
            {
                if(dis[v]>dis[temp]+w)
                dis[v]=dis[temp]+w;
            }
            if(dis[v]>dis[temp]+w)
            {
                dis[v]=dis[temp]+w;
                if(!visit[v])
                {
                    visit[v]=1;
                    q.push(v);
                }
            }
        }
    }
    //for(i=1;i<=n;i++)
    //cout<<dis[i]<<endl;
}
int main()
{
    int i,j,k,l,a,b,c;
    while(scanf("%d",&n),n)
    {
        for(i=0; i<=n; i++)
            g[i].clear();
        int dis1[Max],dis2[Max];
        scanf("%d",&m);
        for(i=0; i<m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            kdq k;
            k.e=b;
            k.w=c;
            g[a].push_back(k);
            k.e=a;
            g[b].push_back(k);
        }
        for(i=1; i<=n; i++)
            scanf("%d",&agree[i]);
        spfa(1,dis1);
        spfa(2,dis2);
        int min=dis1[2]<dis2[1]?dis1[2]:dis2[1];
        for(i=1; i<=n; i++)//更新min找出最小值
        {
            if(min>dis1[i]+dis2[i])
                min=dis1[i]+dis2[i];
        }
        if(min==inf)
            cout<<-1<<endl;
        else
            cout<<min<<endl;
    }
    return 0;
}

水水更健康~