Dijkstra算法（优先队列优化）

注意：we assume that Mr. M starts from city 1 and his target is city 2.

合法路径：1→1,1→2，2→2 非法路径：2→1

  • 距离更新时增加限制：禁止从2转向1
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<climits>
using namespace std;

const int maxn=601;
const int INF=INT_MAX;

struct Point{
    int next;
    int distance;
    bool operator <(Point x)const{
       return distance>x.distance;
    }
    Point(int n,int d):next(n),distance(d){}
    Point(){}
};

struct Edge{
    int to;
    int distance;
    Edge(int t,int d):to(t),distance(d){}
    Edge(){}
};

vector<Edge>graph[maxn];
int dis[maxn];
int leader[maxn];//所属阵营

void Dijkstra(int start,int n){
    fill(dis+1,dis+n+1,INF);
    dis[start]=0;
    
    priority_queue<Point>myqueue;
    myqueue.push(Point(start,0));
    while(!myqueue.empty()){
        int u=myqueue.top().next;
        myqueue.pop();
        for(int i=0;i<graph[u].size();i++){
            int x=graph[u][i].to;
            int y=graph[u][i].distance;
            if(leader[u]==2&&leader[x]==1)continue;//禁止从2到1
            if(dis[u]+y<dis[x]){
                dis[x]=dis[u]+y;
                myqueue.push(Point(x,dis[x]));
            }
        }
    }
}
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0)break;
        memset(graph,0,sizeof(graph));
        for(int i=0;i<m;i++){
            int f,t,d;
            scanf("%d%d%d",&f,&t,&d);
            graph[f].push_back(Edge(t,d));//视为无向边
            graph[t].push_back(Edge(f,d));
        }
        for(int i=1;i<=n;i++)scanf("%d",&leader[i]);

        Dijkstra(1,n);
        if(dis[2]==INF)printf("-1\n");
        else printf("%d\n",dis[2]);
    }
    return 0;
}