10654 | 2024. 04. 07 18:58:15 | 999 | Nagysebességű vasút | cpp17 | Hibás válasz 0/100 | 564ms | 29864 KiB |
// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
#include <queue>
using namespace std;
int main() {
int n,m;cin>>n>>m;
vector<vector<pair<int,int>>> v(n);
for(int i = 0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
v[a].push_back({b,c});
v[b].push_back({a,c});
}
vector<int> disS(n,INT_MAX),disE(n,INT_MAX);
priority_queue<pair<int, int>> q;
disS[0]=0;
disE[n-1]=0;
q.push({0,0});
vector<bool> proc1(n),proc2(n);
while(!q.empty()){
int a=q.top().second;
q.pop();
if(proc1[a])continue;
proc1[a]=true;
for(auto u:v[a]){
int b=u.first,w=u.second;
if(disS[b]>disS[a]+w){
disS[b]=disS[a]+w;
q.push({-disS[b],b});
}
}
}
q.push({0,n-1});
while(!q.empty()){
int a=q.top().second;
q.pop();
if(proc2[a])continue;
proc1[a]=true;
for(auto u:v[a]){
int b=u.first,w=u.second;
if(disE[b]>disE[a]+w){
disE[b]=disE[a]+w;
q.push({-disE[b],b});
}
}
}
int ans=INT_MAX;
for(int i = 0;i<n;i++){
for(auto u : v[i]){
int a=i,b=u.first,c=u.second;
if(disS[a]+disE[b]+c>disS[n-1]){
if(disS[a]+disE[b]+c-disS[n-1]+1<c){//cout<<a<<' '<<b<<endl;
ans=min(ans,disS[a]+disE[b]+c-disS[n-1]+1);
}
}
if(disS[b]+disE[a]+c>disS[n-1]){
if(disS[a]+disE[b]+c-disS[n-1]+1<c){//cout<<a<<' '<<b<<endl;
ans=min(ans,disS[b]+disE[a]+c-disS[n-1]+1);
}
}
}
}cout<<(ans==INT_MAX?-1:ans)<<endl;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1812 KiB | ||||
2 | Hibás válasz | 3ms | 2056 KiB | ||||
subtask2 | 0/35 | ||||||
3 | Hibás válasz | 4ms | 2536 KiB | ||||
4 | Hibás válasz | 4ms | 2752 KiB | ||||
5 | Hibás válasz | 4ms | 2892 KiB | ||||
6 | Hibás válasz | 4ms | 3356 KiB | ||||
7 | Hibás válasz | 4ms | 3164 KiB | ||||
8 | Hibás válasz | 4ms | 3168 KiB | ||||
subtask3 | 0/30 | ||||||
9 | Hibás válasz | 130ms | 15420 KiB | ||||
10 | Hibás válasz | 128ms | 15532 KiB | ||||
11 | Hibás válasz | 128ms | 15748 KiB | ||||
12 | Hibás válasz | 127ms | 15828 KiB | ||||
13 | Hibás válasz | 128ms | 15916 KiB | ||||
14 | Hibás válasz | 133ms | 15960 KiB | ||||
subtask4 | 0/35 | ||||||
15 | Hibás válasz | 564ms | 29556 KiB | ||||
16 | Hibás válasz | 537ms | 29400 KiB | ||||
17 | Hibás válasz | 550ms | 29356 KiB | ||||
18 | Hibás válasz | 529ms | 29656 KiB | ||||
19 | Hibás válasz | 505ms | 29624 KiB | ||||
20 | Hibás válasz | 518ms | 29624 KiB | ||||
21 | Hibás válasz | 495ms | 29532 KiB | ||||
22 | Hibás válasz | 514ms | 29784 KiB | ||||
23 | Hibás válasz | 508ms | 29864 KiB | ||||
24 | Hibás válasz | 261ms | 20964 KiB | ||||
25 | Hibás válasz | 129ms | 16720 KiB | ||||
26 | Hibás válasz | 128ms | 16924 KiB | ||||
27 | Hibás válasz | 133ms | 16844 KiB |