結果
問題 | No.848 なかよし旅行 |
ユーザー |
![]() |
提出日時 | 2019-08-06 15:14:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,292 bytes |
コンパイル時間 | 1,534 ms |
コンパイル使用メモリ | 178,380 KB |
実行使用メモリ | 11,308 KB |
最終ジャッジ日時 | 2024-10-07 03:02:30 |
合計ジャッジ時間 | 3,367 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 24 WA * 2 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef long long ll;class Dijkstra {public:struct edge { long long v, dist; };struct state {long long v, cost;bool operator>(const state s) const { return cost > s.cost; }};const long long INF = (1LL << 60);long long N;vector< vector<edge> > E;Dijkstra(long long n): N(n), E(n) {}//有効グラフの時はこっち。u→vに距離dで結ぶvoid add_directed_edge(long long u, long long v, long long d) {E[u].push_back((edge) { v, d });}//無向グラフの時はこっち。uとvを双方向に距離dで結ぶvoid add_undirected_edge(long long u, long long v, long long d) {E[u].push_back((edge) { v, d });E[v].push_back((edge) { u, d });}//Sを始点として、他の頂点への最短経路を探すvector<long long> shortest_path(long long S) {vector<long long> dp(E.size(), INF);priority_queue<state, vector<state>, greater<state> > q;q.push((state) { S, 0 });while(!q.empty()) {long long v = q.top().v, cost = q.top().cost;q.pop();if(dp[v] <= cost) continue;dp[v] = cost;for(int i=0;i < E[v].size() ; i++) {long long nv = E[v][i].v, ncost = cost + E[v][i].dist;if(dp[nv] > ncost) q.push((state) { nv, ncost });}}return dp;}};signed main(){ios::sync_with_stdio(false);cin.tie(0);int n,m,p,q,t;cin>>n>>m>>p>>q>>t;p--,q--;Dijkstra dij(n);for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;dij.add_undirected_edge(--a,--b,c);}vector<ll> P=dij.shortest_path(p),Q=dij.shortest_path(q),v=dij.shortest_path(0);ll dist = v[p] + P[q] + Q[0];if(dist<=t){cout<<t<<endl;return 0;}dist = max(v[p],v[q]);if(2*(dist)>t){cout<<-1<<endl;return 0;}ll ans=0;for(int i=1;i<n;i++){for(int j=1;j<n;j++){dist = v[i] + max(P[i] + P[j],Q[i] + Q[j]) + v[j];if(dist<=t){ans = max(ans, t-max(P[i] + P[j],Q[i] + Q[j]));}}}cout<<ans<<endl;}