分析了半天题的情况,最后被大佬的一句话点醒了。
大佬原话:
没错,一开始我的分析是,因为1城市是1阵营,2城市是2阵营,所以只要保证连接1和2中间的城市阵营都相等就可以。比如1 2 2 2 2或者1 1 1 1 2,但是万万漏掉了一点就是 可能有1 1 2 2 2这样的情况,即中间不是规律的,但是最重要的一点是只要 过了一次阵营2一次,就不能从阵营2返回阵营1,因为目的地2城市是阵营2,而且只能穿越一次这样的情况。所以只要在dijkstra遍历的时候加一个限制条件就行。
完整代码:
#include<iostream> #include<queue> #include<vector> #include<limits.h> using namespace std; const int maxn=601; struct graph{ int to; int weight; graph(int t,int w):to(t),weight(w){} inline bool operator < (const graph &p)const{ return weight<p.weight; } }; struct Point{ int index; int weight;//源点到index点的weight Point(int i,int w):index(i),weight(w){} inline bool operator < (const Point &p)const{ return weight>p.weight; } }; int dis[maxn][2]; int leader[maxn]; vector<graph> g[maxn]; void init(){ for(int i=0;i<maxn;i++){ g[i].clear(); dis[i][0]=dis[i][1]=INT_MAX; leader[i]=0; } } void dijkstra(int s,int l){ //l:0 or 1 priority_queue<Point> q; dis[s][l]=0; q.push(Point(s,dis[s][l])); bool flag=true; while(!q.empty()){ int u=q.top().index; q.pop(); if(u==2)continue; for(int i=0;i<g[u].size();i++){ int to=g[u][i].to; int weight=g[u][i].weight; int lead=abs(leader[u]-leader[to]); if(!(leader[u]==2&&leader[to]==1)){ //like:1 1 2 2 or 1 2 2 2 or 1 1 1 2 if(dis[to][l]>dis[u][l]+weight){ dis[to][l]=dis[u][l]+weight; q.push(Point(to,dis[to][l])); } } } } } int main(){ int n,m,a,b,t; while(cin>>n){ if(n==0)break; init(); cin>>m; for(int i=0;i<m;i++){ cin>>a>>b>>t; g[a].push_back(graph(b,t)); g[b].push_back(graph(a,t)); } for(int i=1;i<=n;i++){ cin>>leader[i]; } dijkstra(1,0); dijkstra(1,1); cout<<(min(dis[2][0],dis[2][1])==INT_MAX?-1:min(dis[2][0],dis[2][1]))<<endl; } return 0; }