#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 200, M = 5e4 ;
ll n, m, from[M + 1], to[M + 1], c[M + 1], d[M + 1] ;
set<pair<ll, ll>> v[N + 1] ;
ll deikstra(ll city, ll abu)
{
ll dist[N + 1] ;
set<pair<ll, ll>> s ;
for(ll i = 1 ; i <= N ; i++)
dist[i] = 1e15 ;
dist[city] = 0 ;
s.insert({0, city}) ;
while(s.size())
{
pair<ll, ll> p = *s.begin() ;
s.erase(p) ;
// cout << p.fi << ' ' << p.se << '\n' ;
if(p.fi > dist[p.se])
continue ;
for(auto i : v[p.se])
{
if(dist[i.fi] > p.fi + i.se)
{
// cout<<p.se<<"->"<<i.fi<<'\n';
dist[i.fi] = p.fi + i.se ;
s.insert({dist[i.fi], i.fi}) ;
}
}
}
return dist[abu] ;
}
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
cin >> n >> m ;
for(ll i = 1 ; i <= m ; i++)
cin >> from[i] >> to[i] >> c[i] >> d[i] ;
if(m <= 1000)
{
ll ans ;
for(ll i = 1 ; i <= m ; i++)
v[from[i]].insert({to[i], c[i]}) ;
ans = deikstra(1, n) + deikstra(n, 1) ;
for(ll i = 1 ; i <= m ; i++)
{
ll now = d[i] ;
v[from[i]].erase({to[i], c[i]}) ;
v[to[i]].insert({from[i], c[i]}) ;
now += deikstra(1, n) ;
now += deikstra(n, 1) ;
ans = min(ans, now) ;
// cout << "___________________\n" ;
v[to[i]].erase({from[i], c[i]}) ;
v[from[i]].insert({to[i], c[i]}) ;
}
if(ans >= 1e15)
ans = -1 ;
cout << ans ;
return 0 ;
}
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
83 ms |
468 KB |
Output is correct |
4 |
Correct |
87 ms |
344 KB |
Output is correct |
5 |
Correct |
25 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
11 ms |
468 KB |
Output is correct |
10 |
Correct |
109 ms |
472 KB |
Output is correct |
11 |
Correct |
101 ms |
352 KB |
Output is correct |
12 |
Correct |
105 ms |
472 KB |
Output is correct |
13 |
Correct |
47 ms |
360 KB |
Output is correct |
14 |
Correct |
55 ms |
468 KB |
Output is correct |
15 |
Correct |
49 ms |
348 KB |
Output is correct |
16 |
Correct |
54 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
12 ms |
2844 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
444 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Incorrect |
9 ms |
2260 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
83 ms |
468 KB |
Output is correct |
4 |
Correct |
87 ms |
344 KB |
Output is correct |
5 |
Correct |
25 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
11 ms |
468 KB |
Output is correct |
10 |
Correct |
109 ms |
472 KB |
Output is correct |
11 |
Correct |
101 ms |
352 KB |
Output is correct |
12 |
Correct |
105 ms |
472 KB |
Output is correct |
13 |
Correct |
47 ms |
360 KB |
Output is correct |
14 |
Correct |
55 ms |
468 KB |
Output is correct |
15 |
Correct |
49 ms |
348 KB |
Output is correct |
16 |
Correct |
54 ms |
468 KB |
Output is correct |
17 |
Incorrect |
12 ms |
2844 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |