#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <utility>
#include <bitset>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <queue>
#include <cstring>
#include <fstream>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pll pair<ll, ll>
#define plpll pair<ll, pll>
#define pii pair<int, int>
#define f first
#define s second
#define inf 1000000000000000
#define endl '\n'
struct edge{
ll u, v, c, d;
};
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n, m;
cin >> n >> m;
vector<pll> G[n+1], g[n+1];
edge z;
vector<edge> e;
while(m--){
cin >> z.u >> z.v >> z.c >> z.d;
G[z.u].pb(mp(z.v, z.c));
g[z.v].pb(mp(z.u, z.c));
e.pb(z);
}
ll D[n+1], d[n+1], nD[n+1], nd[n+1];
for(int i=0;i<n+1;i++) D[i]=inf;
for(int i=0;i<n+1;i++) d[i]=inf;
for(int i=0;i<n+1;i++) nD[i]=inf;
for(int i=0;i<n+1;i++) nd[i]=inf;
priority_queue<pll, vector<pll>, greater<pll> > pq;
pq.push(mp(0, 1));
while(!pq.empty()){
pll cur=pq.top();
pq.pop();
if(D[cur.s]==inf) D[cur.s]=cur.f;
else continue;
for(pll u:G[cur.s]){
if(D[u.f]!=inf) continue;
pq.push(mp(cur.f+u.s, u.f));
}
}
pq.push(mp(0, 1));
while(!pq.empty()){
pll cur=pq.top();
pq.pop();
if(d[cur.s]==inf) d[cur.s]=cur.f;
else continue;
for(pll u:g[cur.s]){
if(d[u.f]!=inf) continue;
pq.push(mp(cur.f+u.s, u.f));
}
}
pq.push(mp(0, n));
while(!pq.empty()){
pll cur=pq.top();
pq.pop();
if(nD[cur.s]==inf) nD[cur.s]=cur.f;
else continue;
for(pll u:G[cur.s]){
if(nD[u.f]!=inf) continue;
pq.push(mp(cur.f+u.s, u.f));
}
}
pq.push(mp(0, n));
while(!pq.empty()){
pll cur=pq.top();
pq.pop();
if(nd[cur.s]==inf) nd[cur.s]=cur.f;
else continue;
for(pll u:g[cur.s]){
if(nd[u.f]!=inf) continue;
pq.push(mp(cur.f+u.s, u.f));
}
}
/*for(int i=1;i<=n;i++) cout << D[i] << " ";cout << endl;
for(int i=1;i<=n;i++) cout << d[i] << " ";cout << endl;
for(int i=1;i<=n;i++) cout << nD[i] << " ";cout << endl;
for(int i=1;i<=n;i++) cout << nd[i] << " ";cout << endl;*/
ll ans=inf;
for(edge k:e){
if(k.d+min(k.c+D[k.v]+nd[k.u], D[n])+min(k.c+nD[k.v]+d[k.u], nD[1])<ans) ans=k.d+min(k.c+D[k.v]+nd[k.u], D[n])+min(k.c+nD[k.v]+d[k.u], nD[1]);
}
if(ans==inf) cout << "-1\n";
else cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
5316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
