結果

問題 No.848 なかよし旅行
ユーザー totori_nyaa
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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→vd
void add_directed_edge(long long u, long long v, long long d) {
E[u].push_back((edge) { v, d });
}
//uvd
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0