提出番号 | 2230 |
---|---|

提出者 | ndifix |

言語 | C++ |

提出日時 | 2019-05-16 22:56:53 |

問題名 | (49)最短経路問題 |

結果 | AC |

点数 | 100% |

テストケース | 結果 | 得点 | 実行時間 | メモリ使用量 |
---|---|---|---|---|

1 | AC | 100% | 2ms | 8016KB |

2 | AC | 100% | 2ms | 8704KB |

3 | AC | 100% | 2ms | 7856KB |

4 | AC | 100% | 2ms | 8640KB |

5 | AC | 100% | 2ms | 8432KB |

6 | AC | 100% | 6ms | 8432KB |

7 | AC | 100% | 6ms | 7920KB |

8 | AC | 100% | 6ms | 8880KB |

9 | AC | 100% | 6ms | 8672KB |

10 | AC | 100% | 6ms | 8672KB |

11 | AC | 100% | 187ms | 51792KB |

12 | AC | 100% | 186ms | 51792KB |

13 | AC | 100% | 188ms | 51840KB |

14 | AC | 100% | 187ms | 51792KB |

15 | AC | 100% | 172ms | 50752KB |

16 | AC | 100% | 236ms | 52400KB |

17 | AC | 100% | 246ms | 51808KB |

18 | AC | 100% | 250ms | 52368KB |

19 | AC | 100% | 238ms | 52416KB |

20 | AC | 100% | 234ms | 52320KB |

21 | AC | 100% | 236ms | 52288KB |

22 | AC | 100% | 257ms | 52400KB |

23 | AC | 100% | 240ms | 52368KB |

24 | AC | 100% | 244ms | 52384KB |

25 | AC | 100% | 273ms | 52368KB |

26 | AC | 100% | 243ms | 52368KB |

27 | AC | 100% | 233ms | 52352KB |

28 | AC | 100% | 243ms | 52352KB |

29 | AC | 100% | 252ms | 52320KB |

30 | AC | 100% | 245ms | 52400KB |

```
#include <bits/stdc++.h>
#define inf 1000000000
#define mod 1000000007
using namespace std;
using LL = long long;
struct gragh{
int V,E;
std::vector<std::vector<std::pair<int,int>>> edge; //edge[from][i] ={to,cost}
//only for 0-indexed
gragh(int v,int e,int *from,int *to,int *cost){
V=v;E=e; std::pair<int,int>p;
for(int i=0;i<e;i++){
//if(edge.size()<=from[i])edge.resize(from[i]+1);
edge.resize(v);
p.first=to[i]; p.second=cost[i]; edge[from[i]].push_back(p);
p.first=from[i]; p.second=cost[i]; edge[to[i]].push_back(p);
} }
gragh(int v,int e,std::vector<int> &from,std::vector<int> &to,std::vector<int> &cost){
V=v;E=e; std::pair<int,int>p;
for(int i=0;i<e;i++){
//if(edge.size()<=from[i])edge.resize(from[i]+1);
edge.resize(v);
p.first=to[i]; p.second=cost[i]; edge[from[i]].push_back(p);
p.first=from[i]; p.second=cost[i]; edge[to[i]].push_back(p);
} }
int dijkstra(int start,int goal){
int done[V]; for(int i=0;i<V;i++)done[i]=0; done[start]=1;
int vertex[V]; for(int i=0;i<V;i++)vertex[i]=inf; vertex[start]=0;
std::queue<int> que; que.push(start);
int from, to, cost;
while(que.size()!=0){
from=que.front();
for(int i=0; i<edge[from].size(); i++){
to=edge[from][i].first; cost=edge[from][i].second;
if( vertex[to]>vertex[from]+cost){
vertex[to]=vertex[from]+cost;
que.push(to);
}
}
que.pop();
}
return vertex[goal]; }
};
int main(){
int n,m;cin>>n>>m;
vector<int> a(m),b(m),c(m);
for(int i=0;i<m;i++)cin>>a[i]>>b[i]>>c[i];
for(int i=0;i<m;i++){a[i]--;b[i]--;}
gragh G(n,m,a,b,c);
cout<<(G.dijkstra(0,n-1)!=inf?G.dijkstra(0,n-1):-1)<<endl;
}
```