POJ|3767 Dijkstra最短路径

经典的最短路径题目，更新的时候加上一个条件即可，不可以从leader为2的地区到leader为1的地区。

#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>
#include<cstring>
using namespace std;

struct Edge{
    int to;
    int len;
    Edge(int t, int l):to(t), len(l){}
};

struct Point{
    int num;
    int dis;
    bool operator < (const Point& p) const{
        return dis > p.dis;
    }
    Point(int n, int d):num(n), dis(d){}
};

const int MAXN = 601;
const int INF = INT_MAX;

vector<Edge> graph[MAXN];
int leader[MAXN];
int dist[MAXN];

void Dijkstra(int s){
    dist[s] = 0;
    priority_queue<Point> q;
    q.push(Point(s, 0));
    while(!q.empty()){
        int u = q.top().num;
        q.pop();
        for(int i = 0; i < graph[u].size(); i++){
            int v = graph[u][i].to;
            if(leader[u] == 2 && leader[v] == 1)
                continue;
            if(dist[v] > dist[u] + graph[u][i].len){
                dist[v] = dist[u]+graph[u][i].len;
                q.push(Point(v, dist[v]));
            }
        }
    }
    return;
}

int main(){
    int n,m;
    while(cin>>n && n){
        fill(dist, dist+MAXN, INF);
        memset(graph, 0, sizeof(graph));
        cin>>m;  // m条路
        while(m--){
            int from,to,l;
            cin>>from>>to>>l;
            graph[from].push_back(Edge(to, l));
            graph[to].push_back(Edge(from, l));
        }
        for(int i = 1; i <= n; i++){
            int l;
            cin>>l;
            leader[i] = l;
        }
        Dijkstra(1);
        if(dist[2] == INF)
            cout<<-1<<endl;
        else
            cout<<dist[2]<<endl;
    }
    return 0;
}