HDU-6386-最短路

Age of Moyu

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 119 Accepted Submission(s): 23

Problem Description

Mr.Quin love fishes so much and Mr.Quin’s city has a nautical system,consisiting of

Input

There might be multiple test cases, no more than

Output

For each test case output the minimum required cost. If Mr.Quin can’t travel to port

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　　

　　　　题面贼鸡儿难理解，其实就是求最小换乘次数，第一次上路时也算一次换乘。用set维护当前最短路的状态对应的边权，然后跑最短路就好了。用spfa，不断更新，看讨论说bfs也可以做。dij的话也ok，只要不断更新所有的最短路状态就好了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long 
 4 #define mp make_pair
 5 #define pb push_back
 6 #define inf 0x3f3f3f3f
 7 int N,M;
 8 struct Edge{
 9     int v,w,next;
10 }e[400040];
11 int tot,first[101010],d[101010];
12 bool vis[101010];
13 set<int>S[101010];
14 void add(int u,int v,int w){
15     e[tot].v=v;
16     e[tot].w=w;
17     e[tot].next=first[u];
18     first[u]=tot++;
19 }

  　　 int spfa(){
27     memset(vis,0,sizeof(vis));
28     memset(d,inf,sizeof(d));
29     for(int i=1;i<=N;++i)S[i].clear();
30     queue<int>q;
31     q.push(1);
32     d[1]=0;
33     vis[1]=1;
34     while(!q.empty()){
35         int u=q.front();
36         q.pop();
37         vis[u]=0;
38         for(int i=first[u];~i;i=e[i].next){
39             int w;
40             if(S[u].count(e[i].w)) w=d[u];
41             else w=d[u]+1;
42             if(d[e[i].v]>w){
43                 d[e[i].v]=w;
44                 S[e[i].v].clear();
45                 S[e[i].v].insert(e[i].w);
46                 if(!vis[e[i].v]){
47                     q.push(e[i].v);
48                     vis[e[i].v]=1;
49                 }
50             }
51             else if(d[e[i].v]==w&&S[e[i].v].count(e[i].w)==0){
52                 S[e[i].v].insert(e[i].w);
53                     if(!vis[e[i].v]){
54                     q.push(e[i].v);
55                     vis[e[i].v]=1;
56                 }
57             }
58         }
59     }
60     if(d[N]==inf) return -1;    
61     return d[N];
62 }
63 int main(){
64     int i,j,u,v,w;
65     while(scanf("%d%d",&N,&M)!=EOF){
66         memset(first,-1,sizeof(first));
67         tot=0;
68         for(i=1;i<=M;++i){
69             scanf("%d%d%d",&u,&v,&w);
70             add(u,v,w);
71             add(v,u,w);
72         }
73         cout<<spfa()<<endl;
74     }
75     return 0;
76 }

Source

2018 Multi-University Training Contest 7