#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 500000000000LL
int n,m;
int dist[205];
vector<pair<int,int> > adjl[205];
vector<pair<int,int> > rev[205];
int c[50005];
int d[50005];
int adjm[405][405];
vector<pair<pair<int,int>,int> > edges;
main(){
scanf("%lld%lld",&n,&m);
if (m<=1000 ){
for (int x = 0; x<m; x++){
int a,b;
scanf("%lld%lld%lld%lld",&a,&b,&c[x],&d[x]);
adjl[a].push_back({b,x});
rev[b].push_back({a,x});
}
int fans = INF;
for (int cov = -1; cov<m; cov++){
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
for (int x = 0; x<=n; x++){
dist[x] = INF;
}
dist[1] = 0;
pq.push({0,1});
while (!pq.empty()){
int d = pq.top().first;
int node = pq.top().second;
pq.pop();
if (d>dist[node]) continue;
for (auto x : adjl[node]){
if (x.second==cov) continue;
if (dist[node]+c[x.second]<dist[x.first]){
dist[x.first] = dist[node]+c[x.second];
pq.push({dist[x.first],x.first});
}
}
for (auto x : rev[node]){
if (x.second!=cov) continue;
if (dist[node]+c[x.second]<dist[x.first]){
dist[x.first] = dist[node]+c[x.second];
pq.push({dist[x.first],x.first});
}
}
}
int ans = dist[n];
if (ans==INF) continue;
for (int x = 0; x<=n; x++){
dist[x] = INF;
}
dist[n] = 0;
pq.push({0,n});
while (!pq.empty()){
int d = pq.top().first;
int node = pq.top().second;
pq.pop();
if (d>dist[node]) continue;
for (auto x : adjl[node]){
if (x.second==cov) continue;
if (dist[node]+c[x.second]<dist[x.first]){
dist[x.first] = dist[node]+c[x.second];
pq.push({dist[x.first],x.first});
}
}
for (auto x : rev[node]){
if (x.second!=cov) continue;
if (dist[node]+c[x.second]<dist[x.first]){
dist[x.first] = dist[node]+c[x.second];
pq.push({dist[x.first],x.first});
}
}
}
if (dist[1]==INF) continue;
fans = min(fans,ans+dist[1]+d[cov]);
}
printf("%lld",fans==INF?-1:fans);
return 0;
}
for (int x = 0; x<=2*n; x++){
for (int y = 0; y<=2*n; y++){
adjm[x][y] = INF;
if (x==y) adjm[x][y] = 0;
}
}
for (int x = 0; x<m; x++){
int a,b,c,d;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
adjm[a][b] = min(adjm[a][b],c);
adjm[a+n][b+n] = min(adjm[a+n][b+n],c);
adjm[b][a+n] = min(adjm[b][a+n],c+d);
if (x&1)
edges.push_back({{a,b},adjm[b][a+n]-c});
}
for (int k = 1; k<=2*n; k++){
for (int i = 1; i<=2*n; i++){
for (int j = 1; j<=2*n; j++){
adjm[i][j] = min(adjm[i][j],adjm[i][k]+adjm[k][j]);
}
}
}
int ans1 = min(adjm[1][n]+adjm[n][1],adjm[1][2*n]+adjm[2*n][n+1]);
ans1 = min(ans1,adjm[1][n]+adjm[n][n+1]);
for (auto x : edges){
int another = adjm[1][x.first.second]+adjm[x.first.second][x.first.first+n]+adjm[x.first.first+n][n+n];
another += adjm[n][x.first.second] + adjm[x.first.second][x.first.first+n] + adjm[x.first.first+n][n+1];
assert(another>=0);
another -= x.second;
ans1 = min(ans1,another);
}
//assert(ans1>=0);
printf("%lld",ans1>=INF?-1:ans1);
return 0;
}
Compilation message
ho_t4.cpp:15:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&n,&m);
~~~~~^~~~~~~~~~~~~~~~~~
ho_t4.cpp:21:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld",&a,&b,&c[x],&d[x]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
60 ms |
384 KB |
Output is correct |
| 4 |
Correct |
64 ms |
384 KB |
Output is correct |
| 5 |
Correct |
20 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
8 ms |
384 KB |
Output is correct |
| 10 |
Correct |
90 ms |
384 KB |
Output is correct |
| 11 |
Correct |
84 ms |
384 KB |
Output is correct |
| 12 |
Correct |
86 ms |
384 KB |
Output is correct |
| 13 |
Correct |
25 ms |
384 KB |
Output is correct |
| 14 |
Correct |
43 ms |
504 KB |
Output is correct |
| 15 |
Correct |
15 ms |
512 KB |
Output is correct |
| 16 |
Correct |
43 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
2556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
96 ms |
2556 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
60 ms |
384 KB |
Output is correct |
| 4 |
Correct |
64 ms |
384 KB |
Output is correct |
| 5 |
Correct |
20 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
8 ms |
384 KB |
Output is correct |
| 10 |
Correct |
90 ms |
384 KB |
Output is correct |
| 11 |
Correct |
84 ms |
384 KB |
Output is correct |
| 12 |
Correct |
86 ms |
384 KB |
Output is correct |
| 13 |
Correct |
25 ms |
384 KB |
Output is correct |
| 14 |
Correct |
43 ms |
504 KB |
Output is correct |
| 15 |
Correct |
15 ms |
512 KB |
Output is correct |
| 16 |
Correct |
43 ms |
384 KB |
Output is correct |
| 17 |
Incorrect |
97 ms |
2556 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
