#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;
};
struct simple{
ll x, y, id;
};
ll n, m;
edge e[50009];
vector<simple> inc[209];
vector<simple> out[209];
void dijkstra(ll beg, ll dis[], ll used[], ll dont[], vector<simple> g[], ll end, pll prt[]){
for(ll i = 1; i <= n; ++i)
dis[i] = inf;
for(ll i = 0; i < m; ++i)
used[i] = 0;
dis[beg] = 0;
priority_queue<pair<pll, pll>, vector<pair<pll, pll>>, greater<pair<pll, pll>>> pq;
pq.push({{0, beg}, {-1, -1}});
while(!pq.empty()){
int d = pq.top().ff.ff;
int v = pq.top().ff.ss;
int comeid = pq.top().ss.ff;
int comev = pq.top().ss.ss;
pq.pop();
if(dis[v] < d) continue;
if(comeid != -1)
prt[v] = {comeid, comev};
for(auto u : g[v]){
if(dont[u.id]) continue;
if(dis[u.x] > u.y + d){
dis[u.x] = u.y + d;
pq.push({{dis[u.x], u.x}, {u.id , v}});
}
}
}
if(dis[end] >= inf) return;
ll cur = end;
while(cur != beg){
used[prt[cur].ff] = 1;
cur = prt[cur].ss;
}
}
ll frombeg[2][209];
ll usedbeg[2][50009];
ll toend[2][209];
ll usedend[2][50009];
ll emptyar[50009];
ll ans[50009];
pll prt[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 = 0; i < m; ++i){
cin >> e[i].x >> e[i].y >> e[i].z >> e[i].d;
e[i].id = i;
inc[e[i].y].pb({e[i].x, e[i].z, e[i].id});
out[e[i].x].pb({e[i].y, e[i].z, e[i].id});
ans[i] += e[i].d;
}
ll beg = 1;
ll end = n;
ll fin = 0;
dijkstra(beg, frombeg[0], usedbeg[0], emptyar, out, end, prt);
dijkstra(beg, frombeg[1], usedbeg[1], usedbeg[0], out, end, prt);
dijkstra(end, toend[0], usedend[0], emptyar, inc, beg, prt);
dijkstra(end, toend[1], usedend[1], usedend[0], inc, beg, prt);
fin += frombeg[0][end];
for(ll i = 0; i < m; ++i){
ll d = inf;
if(usedbeg[0][i] == 0){
d = min(frombeg[0][end], frombeg[0][e[i].y] + e[i].z + toend[0][e[i].x]);
ans[i] += d;
continue;
}
d = min(frombeg[1][end], frombeg[0][e[i].x]+toend[1][e[i].x]);
d = min(d, frombeg[1][e[i].y]+toend[0][e[i].y]);
ans[i] += d;
}
beg = n;
end = 1;
dijkstra(beg, frombeg[0], usedbeg[0], emptyar, out, end, prt);
dijkstra(beg, frombeg[1], usedbeg[1], usedbeg[0], out, end, prt);
dijkstra(end, toend[0], usedend[0], emptyar, inc, beg, prt);
dijkstra(end, toend[1], usedend[1], usedend[0], inc, beg, prt);
fin += frombeg[0][end];
for(ll i = 0; i < m; ++i){
ll d = inf;
if(usedbeg[0][i] == 0){
d = min(frombeg[0][end], frombeg[0][e[i].y] + e[i].z + toend[0][e[i].x]);
ans[i] += d;
continue;
}
d = min(frombeg[1][end], frombeg[0][e[i].x]+toend[1][e[i].x]);
d = min(d, frombeg[1][e[i].y]+toend[0][e[i].y]);
ans[i] += d;
}
for(ll i = 0; i < m; ++i){
fin = min(fin, ans[i]);
}
if(fin >= inf)
cout << -1;
else
cout << fin;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
6 ms |
640 KB |
Output is correct |
4 |
Correct |
8 ms |
640 KB |
Output is correct |
5 |
Correct |
7 ms |
640 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
512 KB |
Output is correct |
10 |
Correct |
6 ms |
512 KB |
Output is correct |
11 |
Correct |
6 ms |
640 KB |
Output is correct |
12 |
Incorrect |
6 ms |
640 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
8696 KB |
Output is correct |
2 |
Correct |
39 ms |
8952 KB |
Output is correct |
3 |
Correct |
33 ms |
9380 KB |
Output is correct |
4 |
Correct |
7 ms |
768 KB |
Output is correct |
5 |
Correct |
5 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
512 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
32 ms |
9080 KB |
Output is correct |
10 |
Correct |
32 ms |
9088 KB |
Output is correct |
11 |
Correct |
33 ms |
8952 KB |
Output is correct |
12 |
Correct |
33 ms |
9216 KB |
Output is correct |
13 |
Correct |
35 ms |
9208 KB |
Output is correct |
14 |
Correct |
33 ms |
9728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
2 |
Correct |
6 ms |
512 KB |
Output is correct |
3 |
Correct |
25 ms |
6784 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
31 ms |
8960 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
30 ms |
8824 KB |
Output is correct |
9 |
Correct |
31 ms |
8832 KB |
Output is correct |
10 |
Correct |
30 ms |
9080 KB |
Output is correct |
11 |
Correct |
31 ms |
8696 KB |
Output is correct |
12 |
Correct |
29 ms |
9080 KB |
Output is correct |
13 |
Correct |
4 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
4 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
29 ms |
8824 KB |
Output is correct |
20 |
Correct |
31 ms |
8960 KB |
Output is correct |
21 |
Correct |
30 ms |
8824 KB |
Output is correct |
22 |
Correct |
30 ms |
8576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
6 ms |
640 KB |
Output is correct |
4 |
Correct |
8 ms |
640 KB |
Output is correct |
5 |
Correct |
7 ms |
640 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
512 KB |
Output is correct |
10 |
Correct |
6 ms |
512 KB |
Output is correct |
11 |
Correct |
6 ms |
640 KB |
Output is correct |
12 |
Incorrect |
6 ms |
640 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |