2018 Multi-University Training Contest 7 Age of Moyu

2018 Multi-University Training Contest 7 Age of Moyu Age of Moyu

来追梦

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 −1instead)

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

Source

2018 Multi-University Training Contest 7

Recommend

chendu

总结

最开始居然想到纯暴力的dfs了，当然就TLE了。
使用spfa来寻找最短路，需要考虑某一点的最短路是通过什么线路而得来，所以在这里将多个到某点的最短路全部放到队列中，为判断环，使用一个数组来记录，该点达到最初最短路的颜色，然后同种颜色就不处理。发现有问题，两个环同时连接于一点，就会出问题，循环无法结束。
还是按题解说的“用set记录一下每个点当前的最小花费是由哪几种情况转移而来 跑一边最短路即可”比较好

代码

#include
#include
#include
#include

using namespace std;  

const int INF = 0x7f7f7f7f;  
const int  MAXN = 100100;  
const int MAXM = 400100;    
int head[MAXN];
int Next[MAXM];  
int dis[MAXN];  
struct note{
    int u,v,c;  
    note(){} 
    note(int u, int v, int c):u(u), v(v), c(c){}
} p[MAXM];

template
inline bool scan_d(T &ret){
    char c;  int sgn;  
    if( c = getchar(), c==EOF) return 0;  
    while(c!='-' && (c <'0' || c>'9'))c = getchar();  
    sgn = (c=='-') ?-1:1; 
    ret = (c == '-')?0:(c-'0');  
    while(c = getchar(), c>='0' && c<='9') ret = ret*10+(c-'0');  
    ret *= sgn;  
    return 1;  
}

inline void out(int x){
	if(x > 9) out(x/10);  
	putchar(x%10+'0');  
}
int e,n,m;  
inline void addnote(int u, int v, int c){
    p[e]=note(u,v,c);  
    Next[e] = head[u];  
    head[u] = e++;  
}

inline bool relax(int u, int v, int c, int jvli){
    if(dis[v] > jvli + c){
        dis[v] = jvli + c;  
        return true;  
    }
    if(dis[v] == jvli+c)return true;  
    return false;  
}

inline void init(){
    memset(head, -1, sizeof(head));  
    memset(Next, -1, sizeof(Next));  
    e=0;  
    for(int i=0; i a.jvli;   
    }
};

int dyanse[MAXN];  
inline bool spfa(int src){
    memset(dyanse, 0, sizeof(dyanse));  
    for(int i=1; i<=n; i++)
        dis[i] = INF;  
    dis[src] = 0; 
    dyanse[1]=-1;  
    priority_queueque;  que.push(jiedian(src,-1, 0));  
    while(!que.empty()){
        struct jiedian now = que.top();
        int pre = now.dian;
        int yanse = now.yuanxian;  
        int jvli = now.jvli;  
        if(pre == n) return true;  
        que.pop();  
        for(int i=head[pre]; i+1; i=Next[i]){
            if(relax(pre, p[i].v, ((p[i].c==yanse)?0:1),jvli) ){
                if(p[i].c == dyanse[p[i].v])continue;  
                dyanse[p[i].v]=p[i].c;  
                que.push(jiedian(p[i].v,p[i].c, dis[p[i].v]));  
            }
        }
    }
    return true;  
}

int main(){
    //freopen("3.txt", "r", stdin);  
    while(scan_d(n)){
        scan_d(m);  
        init();  
        spfa(1);  
        if(dis[n] == 0x7f7f7f7f)printf("-1n"); 
        else {
        	out(dis[n]);  
        	putchar('n');  
		}
    }
}