#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 && false){
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);
edges.push_back({{a,b},d});
}
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];
another -= x.second;
ans1 = min(ans1,another);
}
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
72 ms |
1664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
96 ms |
4088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
85 ms |
1664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
72 ms |
1664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
