HDU6386 Age of Moyu （dijkstra）

Age of Moyu Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 1384    Accepted Submission(s): 409   Problem Description Mr.Quin love fishes so much and Mr.Quin’s city has a nautical system,consisiting of N ports and M shipping lines. The ports are numbered 1 to N . Each line is occupied by a Weitian. Each Weitian has an identification number. The i -th (1≤i≤M) line connects port Ai and Bi (Ai≠Bi) bidirectionally, and occupied by Ci Weitian (At most one line between two ports). When Mr.Quin only uses lines that are occupied by the same Weitian, the cost is 1 XiangXiangJi. Whenever Mr.Quin changes to a line that is occupied by a different Weitian from the current line, Mr.Quin is charged an additional cost of 1 XiangXiangJi. In a case where Mr.Quin changed from some Weitian A 's line to another Weitian's line changes to Weitian A 's line again, the additional cost is incurred again. Mr.Quin is now at port 1 and wants to travel to port N where live many fishes. Find the minimum required XiangXiangJi (If Mr.Quin can’t travel to port N , print −1 instead)     Input There might be multiple test cases, no more than 20 . You need to read till the end of input. For each test case,In the first line, two integers N (2≤N≤100000) and M (0≤M≤200000) , representing the number of ports and shipping lines in the city. In the following m lines, each contain three integers, the first and second representing two ends Ai and Bi of a shipping line (1≤Ai,Bi≤N) and the third representing the identification number Ci (1≤Ci≤1000000) of Weitian who occupies this shipping line.     Output For each test case output the minimum required cost. If Mr.Quin can’t travel to port N , output −1 instead.     Sample Input   3 3 1 2 1 1 3 2 2 3 1 2 0 3 2 1 2 1 2 3 2     Sample Output   1 -1 2

改一下dijkstra内部函数就ok了

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=1000010;
struct qnode
{
    int v;
    int c;
    int nowline;
    bool operator <(const qnode &r)const
    {
        return c>r.c;
    }
};
struct Edge
{
    int v,cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost) {}
};
vector<Edge>E[MAXN];
bool vis[MAXN];
int dist[MAXN];
void Dijkstra(int n,int start)//点的编号从1开始
{
    memset(vis,false,sizeof(vis));
    memset(dist,INF,sizeof(dist));
    priority_queue<qnode>que;
    while(!que.empty())que.pop();
    dist[start]=0;
    que.push((qnode){start,0,-1});
    qnode tmp;
    while(!que.empty())
    {
        tmp=que.top();
        que.pop();
        int u=tmp.v;
        if(vis[u])continue;
        vis[u]=true;
        for(int i=0; i<E[u].size(); i++)
        {
            // cout<<"eee"<<endl;
            int v=E[tmp.v][i].v;
            int cost=E[u][i].cost;
            // cout<<u<<" "<<v<<" "<<cost<<endl;
            if(cost!=tmp.nowline)
                cost=1;
            else
                cost=0;
            if(!vis[v]&&dist[v]>dist[u]+cost)
            {
                dist[v]=dist[u]+cost;
                que.push((qnode){v,dist[v],E[u][i].cost});
            }
        }
    }
}
void addedge(int u,int v,int w)
{
    E[u].push_back(Edge(v,w));
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<MAXN;i++)
            E[i].clear();
        while(m--){
            int aa,bb,cc;
            scanf("%d%d%d",&aa,&bb,&cc);
            addedge(aa,bb,cc);
            addedge(bb,aa,cc);
        }
        Dijkstra(n,1);
        int ans=dist[n];
        if(dist[n]>=INF)
            printf("-1\n");
        else
            printf("%d\n",ans);
    }
}