ARC 061 E すぬけ君と地下旅行(600)

グラフの変形をする

600点問題ではない

最短経路問題なので、Dijkstraしやすいようにグラフをつくる

辺の数を少なくするため、経由地的な頂点を使う

1. #include<iostream>
2. #include<algorithm>
3. #include<vector>
4. #include<queue>
5. #define lol(i,n) for(int i=0;i<n;i++)
6. #define mod 1000000007
7. typedef long long ll;
8. using namespace std;
10. #include<map>
11. typedef pair<int,int> P;
13. vector<vector<P> >v;//辺リスト(v[i]には辺が詰まっている
14. map<int,int> u[100010];//頂点リスト(u[頂点][路線]==vでの番号)
16. priority_queue<P,vector<P>,greater<P> >Q;
17. int dis[500010];
19. int main(){
20. vector<P> emptyvector;
21. v.push_back(emptyvector);
23. int n,m;
24. cin>>n>>m;
25. int vsize=1;
26. for(int i=1;i<=n;i++){
27. v.push_back(emptyvector);
28. u[i][-1]=vsize;
29. vsize++;
30. }
31. while(m--){
32. int a,b,train;
33. cin>>a>>b>>train;
34. lol(p,2){
35. if(u[a][train]==0){
36. v.push_back(emptyvector);
37. v[vsize].push_back(make_pair(a,0));
38. v[a].push_back(make_pair(vsize,1));
40. u[a][train]=vsize;
41. a=vsize;
42. vsize++;
43. }
44. else{
45. a=u[a][train];
46. }
47. swap(a,b);
48. }
49. v[a].push_back(make_pair(b,0));
50. v[b].push_back(make_pair(a,0));
51. }
53. //↓ Dijkstra ↓
54. lol(i,vsize)dis[i]=mod;
55. Q.push(make_pair(0,1));
56. while(!Q.empty()){
57. int b=Q.top().first,a=Q.top().second;
58. Q.pop();
59. if(dis[a]<=b)continue;
60. dis[a]=b;
61. for(int i=0;i<v[a].size();i++){
62. int pnt=v[a][i].first,cost=v[a][i].second+b;
63. if(dis[pnt]<=cost)continue;
64. Q.push(make_pair(v[a][i].second+b,v[a][i].first));
65. }
66. }
67. int tmp=dis[u[n][-1]];
68. cout<<(tmp==mod?-1:tmp)<<endl;
69. return 0;
70. }

 グラフでも計算量の確認が大事(特に辺の数)