HDU-6386 Age of Moyu （想法+迪杰斯特拉）

Age of Moyu

题目链接： Age of Moyu

---

题意

给你N个顶点，M条边，每条边都属于一个海贼，在从一个海贼的边到另一个海贼的边时需要交1点路费，如果还是同一个海贼，则不用交。

---

思路

现在问题的核心在于，我们原先是直接贪心的找一条最短边，加入进来，但是现在如果直接确定最短路，非常难，因为不知道前一个航道的情况，那么我们就可以用一个set来到达当前点最短路时，可能会有哪些情况。这里就必须要使用堆优化的迪杰斯特拉了。而在每个点，到达这里最短时，不一定只有这一个，所以如果出现相等的情况，那我们就直接将这种航道情况加入set即可。

---

代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define per(i,j,k) for(int i = (int)j;i >= (int)k;i --)
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back

typedef double db;
typedef long long ll;
const int MAXN = (int)1e5+7;
const int INF = (int)0x3f3f3f3f;

struct Node {
    int to,cost;
    Node(int to = 0,int cost = 0):to(to),cost(cost){}
    bool operator < (const Node& a) const {
        return a.cost < cost;
    }
};

struct Peo {
    int to,shu;
    Peo(int to = 0,int shu = 0):to(to),shu(shu){}
};

int N,M;
set<int> se[MAXN];
priority_queue<Node> qu;
vector<Peo> E[MAXN];
int dis[MAXN];

inline int Djs() {
    dis[1] = 0;
    qu.push(Node(1,0));
    while (!qu.empty()) {
        Node k = qu.top();qu.pop();
        rep(i,0,E[k.to].size()-1) {
            int to = E[k.to][i].to;
            int shu = E[k.to][i].shu;
            int cost = k.cost + !se[k.to].count(shu);
            if (dis[to] > cost) {
                dis[to] = cost;
                se[to].clear();
                se[to].insert(E[k.to][i].shu);
                qu.push(Node(to,cost));
            }else if (dis[to] == cost) {
                se[to].insert(shu);
            }
        }
    }
    return dis[N]==INF?-1:dis[N];
}

inline void init() {
    while (!qu.empty()) qu.pop();
    rep(i,1,N) E[i].clear();
    rep(i,1,N) dis[i] = INF;
}

int main()
{
    while(scanf("%d %d",&N,&M) == 2) {
        init();
        rep(i,1,M) {
            int u,v,c;
            scanf("%d %d %d",&u,&v,&c);
            E[v].pb(Peo(u,c));
            E[u].pb(Peo(v,c));
        }
        printf("%d\n",Djs());
    }
}