#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=1e17;
struct graph{
vector<vector<pair<int,int> > >adi;
vector<int> c;
vector<int> d;
graph(int n, int m){
adi.assign(n, {});
c.assign(m, 0);
d.assign(m, 0);
}
};
void dijkstra(int start, vector<int>& dist, int n, graph& g){
dist.assign(n, INF);
vector<bool> vis(n, false);
priority_queue<pair<int,int> > pq;
dist[start]=0;
pq.push({-0, start});
while(!pq.empty()){
int v=pq.top().second;
pq.pop();
if(vis[v]){
continue;
}
vis[v]=true;
for(auto [u, ind]: g.adi[v]){
if(dist[v]+g.c[ind] < dist[u]){
dist[u] = dist[v] + g.c[ind];
pq.push({-dist[u], u});
}
}
}
}
vector<int> find_sp(int a, int b, vector<int>& froma, vector<int>& tob, graph& g, int m){
vector<int> p;
int dist=froma[b];
assert(froma[b] == tob[a]);
if(dist==INF) return {};
int v=a;
vector<bool> vis(m, false);
while(v!=b){
for(auto [u, ind]: g.adi[v]){
if(vis[ind]) continue;
if(froma[v] + g.c[ind] + tob[u] == dist){
p.push_back(ind);
vis[ind]=true;
v=u;
break;
}
}
}
return p;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
graph g(n, m);
graph rev(n, m);
vector<pair<int,int> > edge(m);
for(int i=0; i<m; i++){
int a, b;
cin >> a >> b >> g.c[i] >> g.d[i];
a--; b--;
g.adi[a].push_back({b, i});
rev.c[i]=g.c[i];
rev.d[i]=g.d[i];
rev.adi[b].push_back({a, i});
edge[i]={a, b};
}
//distances
vector<int> from0(n, INF);
dijkstra(0, from0, n, g);
vector<int> to0(n, INF);
dijkstra(0, to0, n, rev);
vector<int> fromn(n, INF);
dijkstra(n-1, fromn, n, g);
vector<int> ton(n, INF);
dijkstra(n-1, ton, n, rev);
//paths
vector<int> path1=find_sp(0, n-1, from0, ton, g, m);
vector<int> path2=find_sp(n-1, 0, fromn, to0, g, m);
cout << "blub\n";
return 0;
vector<bool> used(m, false);
for(auto e: path1){
used[e]=true;
}
for(auto e: path2){
used[e]=true;
}
//possibility 0: turning no edge
int ans=INF;
ans = min(ans, from0[n-1] + fromn[0]);
//possibility 1: edge not on path
for(int i=0; i<m; i++){
if(used[i]) continue;
auto [a, b]=edge[i];
int d1=from0[b] + g.c[i] + ton[a] + fromn[0];
int d2=from0[n-1] + fromn[b] + g.c[i] + to0[a];
int d=min(d1, d2) + g.d[i];
ans=min(ans, d);
}
//possibility 2: edge on path
vector<int> path=path1;
for(auto e: path2) path.push_back(e);
for(auto e: path){
graph neu(n, m);
for(int i=0; i<m; i++){
neu.c[i]=g.c[i];
neu.d[i]=g.d[i];
auto [a, b]=edge[i];
if(i==e){
neu.adi[b].push_back({a, i});
}
else{
neu.adi[a].push_back({b, i});
}
}
int d=0;
vector<int> dist(n, INF);
dijkstra(0, dist, n, neu);
d=dist[n-1];
dijkstra(n-1, dist, n, neu);
d+=dist[0];
ans=min(ans, d);
}
//output
if(ans==INF){
cout << -1 << "\n";
}
else{
cout << ans << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1079 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
5332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1079 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
