#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 200;
const int MAXM = 5e4;
const ll INF = 1e15;
struct Edge
{
int u, v, p; ll c, d;
};
struct Queue
{
int u, p; ll w;
bool operator < (const Queue &p) const { return w>p.w; }
};
int N, M;
vector<Edge> adj[MAXN+10], radj[MAXN+10];
Edge E[MAXM+10];
ll D1[MAXN+10], DR1[MAXN+10], D2[MAXN+10], DR2[MAXN+10], D[MAXN+10];
int T1[MAXM+10], TR1[MAXM+10], T2[MAXM+10], TR2[MAXM+10], T[MAXM+10];
ll V[MAXM+10];
void dijk(int S, vector<Edge> *aadj, ll *DD, int *TT)
{
int i, j;
priority_queue<Queue> PQ;
for(i=1; i<=N; i++) DD[i]=INF;
for(i=1; i<=M; i++) TT[i]=0;
PQ.push({S, -1, 0});
while(!PQ.empty())
{
Queue now=PQ.top(); PQ.pop();
if(DD[now.u]<=now.w) continue;
DD[now.u]=now.w;
if(now.p>0) TT[now.p]=1;
for(auto nxt : aadj[now.u]) PQ.push({nxt.v, nxt.p, now.w+nxt.c});
}
}
int main()
{
int i, j;
scanf("%d%d", &N, &M);
for(i=1; i<=M; i++)
{
int u, v, c, d;
scanf("%d%d%d%d", &u, &v, &c, &d);
E[i]={u, v, i, c, d};
adj[u].push_back({u, v, i, c, d});
radj[v].push_back({v, u, i, c, d});
}
dijk(1, adj, D1, T1);
dijk(1, radj, DR1, TR1);
dijk(N, adj, D2, T2);
dijk(N, radj, DR2, TR2);
for(i=1; i<=M; i++) V[i]+=E[i].d;
for(i=1; i<=M; i++)
{
if(T1[i])
{
for(auto &it : adj[E[i].u]) if(it.p==i) it.c=INF;
adj[E[i].v].push_back({E[i].v, E[i].u, i, E[i].c, E[i].d});
dijk(1, adj, D, T);
V[i]+=D[N];
adj[E[i].v].pop_back();
for(auto &it : adj[E[i].u]) if(it.p==i) it.c=E[i].c;
}
else
{
ll t=D1[N];
t=min(t, D1[E[i].v]+DR2[E[i].u]+E[i].c);
V[i]+=t;
}
}
for(i=1; i<=M; i++)
{
if(T2[i])
{
for(auto &it : adj[E[i].u]) if(it.p==i) it.c=INF;
adj[E[i].v].push_back({E[i].v, E[i].u, i, E[i].c, E[i].d});
dijk(N, adj, D, T);
V[i]+=D[1];
adj[E[i].v].pop_back();
for(auto &it : adj[E[i].u]) if(it.p==i) it.c=E[i].c;
}
else
{
ll t=D2[1];
t=min(t, D2[E[i].v]+DR1[E[i].u]+E[i].c);
V[i]+=t;
}
}
ll ans=INF;
ans=min(ans, D1[N]+D2[1]);
for(i=1; i<=M; i++) ans=min(ans, V[i]);
if(ans==INF) ans=-1;
printf("%lld\n", ans);
}
Compilation message
ho_t4.cpp: In function 'void dijk(int, std::vector<Edge>*, ll*, int*)':
ho_t4.cpp:32:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:50:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
ho_t4.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &u, &v, &c, &d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
40 ms |
512 KB |
Output is correct |
4 |
Correct |
41 ms |
512 KB |
Output is correct |
5 |
Correct |
11 ms |
512 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 |
7 ms |
512 KB |
Output is correct |
10 |
Correct |
43 ms |
640 KB |
Output is correct |
11 |
Correct |
42 ms |
632 KB |
Output is correct |
12 |
Correct |
42 ms |
632 KB |
Output is correct |
13 |
Correct |
12 ms |
512 KB |
Output is correct |
14 |
Correct |
26 ms |
512 KB |
Output is correct |
15 |
Correct |
26 ms |
512 KB |
Output is correct |
16 |
Correct |
26 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1090 ms |
10184 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
512 KB |
Output is correct |
2 |
Correct |
6 ms |
384 KB |
Output is correct |
3 |
Correct |
922 ms |
7880 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Execution timed out |
1086 ms |
9996 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
40 ms |
512 KB |
Output is correct |
4 |
Correct |
41 ms |
512 KB |
Output is correct |
5 |
Correct |
11 ms |
512 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 |
7 ms |
512 KB |
Output is correct |
10 |
Correct |
43 ms |
640 KB |
Output is correct |
11 |
Correct |
42 ms |
632 KB |
Output is correct |
12 |
Correct |
42 ms |
632 KB |
Output is correct |
13 |
Correct |
12 ms |
512 KB |
Output is correct |
14 |
Correct |
26 ms |
512 KB |
Output is correct |
15 |
Correct |
26 ms |
512 KB |
Output is correct |
16 |
Correct |
26 ms |
512 KB |
Output is correct |
17 |
Execution timed out |
1090 ms |
10184 KB |
Time limit exceeded |
18 |
Halted |
0 ms |
0 KB |
- |