#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
const ll inf = 1e18;
struct edge{
ll x, y, z, d, id;
};
edge e[50009];
ll n, m;
ll dis[209][209];
vector<edge> g[209];
void calcdepth(ll beg, ll depth[]){
queue<ll> q;
q.push(beg);
for(ll i = 1; i <= n; ++i)
depth[i] = inf;
depth[beg] = 0;
while(q.size()){
ll v = q.front();
q.pop();
for(edge u : g[v])
if(dis[u.x][beg] == dis[v][beg] + u.z && depth[u.x] == inf){
depth[u.x] = depth[v]+1;
q.push(u.x);
}
}
}
ll d1[209];
ll dn[209];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> m;
for(ll i = 1; i <= n; ++i)
for(ll j = 1; j <= n; ++j)
if(i != j) dis[i][j] = inf;
for(ll i = 0; i < m; ++i){
cin >> e[i].x >> e[i].y >> e[i].z >> e[i].d;
e[i].id = i;
dis[e[i].x][e[i].y] = min(dis[e[i].x][e[i].y], e[i].z);
g[e[i].y].pb(e[i]);
}
for(ll k = 1; k <= n; ++k)
for(ll i = 1; i <= n; ++i)
for(ll j = 1; j <= n; ++j)
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
calcdepth(1, d1);
calcdepth(n, dn);
ll ans = dis[1][n]+dis[n][1];
for(ll i = 0; i < m; ++i){
edge u = e[i];
ll cur = e[i].d;
if(dn[u.y]+1 == dn[u.x]){
cur += min(dis[n][1], dis[n][u.x]+u.z+dis[u.y][1]);
ll di = inf;
for(ll j = 1; j <= n; ++j)
if(dn[j] == dn[u.y])
for(auto u : g[j])
if(u.id != i)
di = min(di, dis[1][u.x]+u.z+dis[u.z][n]);
if(dn[1] <= dn[u.y])
di = dis[1][n];
cur += di;
}
else if(d1[u.y]+1 == d1[u.x]){
cur += min(dis[1][n], dis[1][u.x]+u.z+dis[u.y][n]);
ll di = inf;
for(ll j = 1; j <= n; ++j)
if(d1[j] == d1[u.y])
for(auto u : g[j])
if(u.id != i)
di = min(di, dis[n][u.x]+u.z+dis[u.z][1]);
if(d1[n] <= d1[u.y])
di = dis[n][1];
cur += di;
}
else{
cur += min(dis[1][n], dis[1][u.y]+u.z+dis[u.x][n]);
cur += min(dis[n][1], dis[n][u.y]+u.z+dis[u.x][1]);
}
ans = min(ans, cur);
}
if(ans >= inf)
cout << -1;
else
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
768 KB |
Output is correct |
2 |
Correct |
14 ms |
640 KB |
Output is correct |
3 |
Runtime error |
16 ms |
1408 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
41 ms |
11128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
768 KB |
Output is correct |
2 |
Correct |
14 ms |
640 KB |
Output is correct |
3 |
Correct |
716 ms |
4992 KB |
Output is correct |
4 |
Correct |
13 ms |
768 KB |
Output is correct |
5 |
Execution timed out |
1092 ms |
6528 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
768 KB |
Output is correct |
2 |
Correct |
14 ms |
640 KB |
Output is correct |
3 |
Runtime error |
16 ms |
1408 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |