#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
#define int ll
#define pb push_back
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define remin(a,b) a = min(a,b)
typedef map<int,int> mii;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define sfl2(x,y) scanf("%lld%lld",&x,&y);
#define pfi(x) printf("%d\n",x);
#define pfl(x) printf("%lld\n",x);
const int INF=1e16;
void solvethetestcase();
signed main(){
int t = 1;
// (UNCOMMENT FOR MULTIPLE TEST CASES) \
sfl(t);
FOR(testcase,1,t+1){
// (UNCOMMENT FOR CODEJAM) \
printf("Case #%lld: ",testcase);
solvethetestcase();
}
}
int n,m;
vector<pair<pii,pii> > edges;
vi adj[205];
int dist[205][205];
int p1[205],p2[205];
int lol[205];
set<int> s;
int dijkstra(){
REP(i,205) lol[i] = INF;
lol[1] = 0;
priority_queue<pii,vpii,greater<pii> > pq;
pq.push({0,1});
while(pq.size()){
int u = pq.top().S;
pq.pop();
for(auto e:adj[u]){
int v = edges[e].F.S,w = edges[e].S.F;
if(lol[v] > lol[u]+w){
lol[v] = lol[u]+w;
pq.push({lol[v],v});
p1[v] = e;
}
}
}
int res = lol[n];
REP(i,205) lol[i] = INF;
lol[n] = 0;
pq.push({0,n});
while(pq.size()){
int u = pq.top().S;
pq.pop();
for(auto e:adj[u]){
int v = edges[e].F.S,w = edges[e].S.F;
if(lol[v] > lol[u]+w){
lol[v] = lol[u]+w;
pq.push({lol[v],v});
p2[v] = e;
}
}
}
return res+lol[1];
}
void solvethetestcase(){
sfl2(n,m)
REP(i,205){
p1[i] = -1;
p2[i] = -1;
REP(j,205){
dist[i][j] = INF;
}
dist[i][i] = 0;
}
REP(i,m){
int u,v,c,d;
sfl2(u,v)
sfl2(c,d)
edges.pb({{u,v},{c,d}});
adj[u].pb(i);
adj[v].pb(i);
remin(dist[u][v],c);
}
FOR(k,1,n+1){
FOR(i,1,n+1){
FOR(j,1,n+1){
remin(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
int ans = dist[1][n]+dist[n][1];
dijkstra();
// trace(dijkstra(),ans);
FOR(i,1,n+1){
// trace(i,p1[i],p2[i]);
if(p1[i] != -1) s.insert(p1[i]);
if(p2[i] != -1) s.insert(p2[i]);
}
REP(i,m){
if(s.find(i) == s.end()){
// trace(i,edges[i].S.S,dist[1][edges[i].F.S],dist[edges[i].F.F][n],edges[i].S.F);
remin(ans,edges[i].S.S+min(dist[1][n],dist[1][edges[i].F.S]+dist[edges[i].F.F][n]+edges[i].S.F)+min(dist[n][1],dist[n][edges[i].F.S]+dist[edges[i].F.F][1]+edges[i].S.F));
}
else{
swap(edges[i].F.F,edges[i].F.S);
// trace(i,dijkstra(),edges[i].S.S);
remin(ans,dijkstra()+edges[i].S.S);
swap(edges[i].F.F,edges[i].F.S);
}
}
if(ans > 1LL*(1e12)) pfi(-1)
else pfl(ans)
}
Compilation message
ho_t4.cpp:57:2: warning: multi-line comment [-Wcomment]
// (UNCOMMENT FOR MULTIPLE TEST CASES) \
^
ho_t4.cpp:60:3: warning: multi-line comment [-Wcomment]
// (UNCOMMENT FOR CODEJAM) \
^
ho_t4.cpp: In function 'void solvethetestcase()':
ho_t4.cpp:45:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define sfl2(x,y) scanf("%lld%lld",&x,&y);
~~~~~^~~~~~~~~~~~~~~~~~
ho_t4.cpp:112:2: note: in expansion of macro 'sfl2'
sfl2(n,m)
^~~~
ho_t4.cpp:45:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define sfl2(x,y) scanf("%lld%lld",&x,&y);
~~~~~^~~~~~~~~~~~~~~~~~
ho_t4.cpp:123:3: note: in expansion of macro 'sfl2'
sfl2(u,v)
^~~~
ho_t4.cpp:45:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define sfl2(x,y) scanf("%lld%lld",&x,&y);
~~~~~^~~~~~~~~~~~~~~~~~
ho_t4.cpp:124:3: note: in expansion of macro 'sfl2'
sfl2(c,d)
^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
768 KB |
Output is correct |
2 |
Correct |
13 ms |
640 KB |
Output is correct |
3 |
Correct |
32 ms |
768 KB |
Output is correct |
4 |
Correct |
35 ms |
768 KB |
Output is correct |
5 |
Correct |
7 ms |
768 KB |
Output is correct |
6 |
Correct |
14 ms |
640 KB |
Output is correct |
7 |
Correct |
5 ms |
640 KB |
Output is correct |
8 |
Correct |
5 ms |
640 KB |
Output is correct |
9 |
Correct |
6 ms |
768 KB |
Output is correct |
10 |
Correct |
37 ms |
880 KB |
Output is correct |
11 |
Correct |
42 ms |
768 KB |
Output is correct |
12 |
Correct |
40 ms |
776 KB |
Output is correct |
13 |
Correct |
18 ms |
768 KB |
Output is correct |
14 |
Correct |
25 ms |
768 KB |
Output is correct |
15 |
Correct |
23 ms |
768 KB |
Output is correct |
16 |
Correct |
24 ms |
768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
846 ms |
3572 KB |
Output is correct |
2 |
Correct |
852 ms |
3572 KB |
Output is correct |
3 |
Correct |
839 ms |
3572 KB |
Output is correct |
4 |
Correct |
34 ms |
768 KB |
Output is correct |
5 |
Correct |
21 ms |
768 KB |
Output is correct |
6 |
Correct |
14 ms |
640 KB |
Output is correct |
7 |
Correct |
14 ms |
640 KB |
Output is correct |
8 |
Correct |
5 ms |
640 KB |
Output is correct |
9 |
Correct |
241 ms |
3572 KB |
Output is correct |
10 |
Correct |
212 ms |
3572 KB |
Output is correct |
11 |
Correct |
556 ms |
3564 KB |
Output is correct |
12 |
Correct |
545 ms |
3572 KB |
Output is correct |
13 |
Correct |
511 ms |
3572 KB |
Output is correct |
14 |
Correct |
409 ms |
3684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
768 KB |
Output is correct |
2 |
Correct |
14 ms |
640 KB |
Output is correct |
3 |
Correct |
225 ms |
3572 KB |
Output is correct |
4 |
Correct |
14 ms |
640 KB |
Output is correct |
5 |
Correct |
261 ms |
3572 KB |
Output is correct |
6 |
Correct |
5 ms |
640 KB |
Output is correct |
7 |
Correct |
5 ms |
640 KB |
Output is correct |
8 |
Correct |
101 ms |
3572 KB |
Output is correct |
9 |
Correct |
120 ms |
3572 KB |
Output is correct |
10 |
Correct |
185 ms |
3572 KB |
Output is correct |
11 |
Correct |
161 ms |
3572 KB |
Output is correct |
12 |
Correct |
182 ms |
3704 KB |
Output is correct |
13 |
Correct |
5 ms |
640 KB |
Output is correct |
14 |
Correct |
5 ms |
640 KB |
Output is correct |
15 |
Correct |
4 ms |
640 KB |
Output is correct |
16 |
Correct |
5 ms |
640 KB |
Output is correct |
17 |
Correct |
5 ms |
640 KB |
Output is correct |
18 |
Correct |
5 ms |
640 KB |
Output is correct |
19 |
Correct |
189 ms |
3572 KB |
Output is correct |
20 |
Correct |
164 ms |
3572 KB |
Output is correct |
21 |
Correct |
174 ms |
3572 KB |
Output is correct |
22 |
Correct |
170 ms |
3564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
768 KB |
Output is correct |
2 |
Correct |
13 ms |
640 KB |
Output is correct |
3 |
Correct |
32 ms |
768 KB |
Output is correct |
4 |
Correct |
35 ms |
768 KB |
Output is correct |
5 |
Correct |
7 ms |
768 KB |
Output is correct |
6 |
Correct |
14 ms |
640 KB |
Output is correct |
7 |
Correct |
5 ms |
640 KB |
Output is correct |
8 |
Correct |
5 ms |
640 KB |
Output is correct |
9 |
Correct |
6 ms |
768 KB |
Output is correct |
10 |
Correct |
37 ms |
880 KB |
Output is correct |
11 |
Correct |
42 ms |
768 KB |
Output is correct |
12 |
Correct |
40 ms |
776 KB |
Output is correct |
13 |
Correct |
18 ms |
768 KB |
Output is correct |
14 |
Correct |
25 ms |
768 KB |
Output is correct |
15 |
Correct |
23 ms |
768 KB |
Output is correct |
16 |
Correct |
24 ms |
768 KB |
Output is correct |
17 |
Correct |
846 ms |
3572 KB |
Output is correct |
18 |
Correct |
852 ms |
3572 KB |
Output is correct |
19 |
Correct |
839 ms |
3572 KB |
Output is correct |
20 |
Correct |
34 ms |
768 KB |
Output is correct |
21 |
Correct |
21 ms |
768 KB |
Output is correct |
22 |
Correct |
14 ms |
640 KB |
Output is correct |
23 |
Correct |
14 ms |
640 KB |
Output is correct |
24 |
Correct |
5 ms |
640 KB |
Output is correct |
25 |
Correct |
241 ms |
3572 KB |
Output is correct |
26 |
Correct |
212 ms |
3572 KB |
Output is correct |
27 |
Correct |
556 ms |
3564 KB |
Output is correct |
28 |
Correct |
545 ms |
3572 KB |
Output is correct |
29 |
Correct |
511 ms |
3572 KB |
Output is correct |
30 |
Correct |
409 ms |
3684 KB |
Output is correct |
31 |
Correct |
23 ms |
768 KB |
Output is correct |
32 |
Correct |
14 ms |
640 KB |
Output is correct |
33 |
Correct |
225 ms |
3572 KB |
Output is correct |
34 |
Correct |
14 ms |
640 KB |
Output is correct |
35 |
Correct |
261 ms |
3572 KB |
Output is correct |
36 |
Correct |
5 ms |
640 KB |
Output is correct |
37 |
Correct |
5 ms |
640 KB |
Output is correct |
38 |
Correct |
101 ms |
3572 KB |
Output is correct |
39 |
Correct |
120 ms |
3572 KB |
Output is correct |
40 |
Correct |
185 ms |
3572 KB |
Output is correct |
41 |
Correct |
161 ms |
3572 KB |
Output is correct |
42 |
Correct |
182 ms |
3704 KB |
Output is correct |
43 |
Correct |
5 ms |
640 KB |
Output is correct |
44 |
Correct |
5 ms |
640 KB |
Output is correct |
45 |
Correct |
4 ms |
640 KB |
Output is correct |
46 |
Correct |
5 ms |
640 KB |
Output is correct |
47 |
Correct |
5 ms |
640 KB |
Output is correct |
48 |
Correct |
5 ms |
640 KB |
Output is correct |
49 |
Correct |
189 ms |
3572 KB |
Output is correct |
50 |
Correct |
164 ms |
3572 KB |
Output is correct |
51 |
Correct |
174 ms |
3572 KB |
Output is correct |
52 |
Correct |
170 ms |
3564 KB |
Output is correct |
53 |
Correct |
918 ms |
3564 KB |
Output is correct |
54 |
Correct |
979 ms |
3572 KB |
Output is correct |
55 |
Correct |
927 ms |
3564 KB |
Output is correct |
56 |
Correct |
35 ms |
768 KB |
Output is correct |
57 |
Correct |
32 ms |
768 KB |
Output is correct |
58 |
Correct |
532 ms |
3564 KB |
Output is correct |
59 |
Correct |
668 ms |
3572 KB |
Output is correct |
60 |
Correct |
933 ms |
3568 KB |
Output is correct |
61 |
Correct |
498 ms |
3700 KB |
Output is correct |
62 |
Correct |
607 ms |
3572 KB |
Output is correct |
63 |
Correct |
889 ms |
3568 KB |
Output is correct |
64 |
Execution timed out |
1095 ms |
3572 KB |
Time limit exceeded |
65 |
Halted |
0 ms |
0 KB |
- |