#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e12 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "
const ll MAX_N = 2e2 + 10, MAX_W = 1e5 + 10;
vector<pair<pair<ll, ll>, pair<ll, ll> > > edges;
bitset<MAX_W> off;
vector<pair<pair<ll, ll>, ll> > g[MAX_N];
ll dist[4][MAX_N];
ll n, m;
void dij(ll ind, ll start) {
for(ll i = 0; i < MAX_N; i ++) {
dist[ind][i] = mod;
}
priority_queue<pair<ll, ll> > pq;
pq.push({0, start});
dist[ind][start] = 0;
while(!pq.empty()) {
auto curr = pq.top(); pq.pop();
curr.first *= -1;
for(auto it : g[curr.second]) {
if(off[it.second]) {continue;}
ll nxt = it.first.first;
if(dist[ind][nxt] > curr.first + it.first.second) {
dist[ind][nxt] = curr.first + it.first.second;
pq.push({-dist[ind][nxt], nxt});
}
}
}
return;
cout << "Started from " << start << endl;
for(ll i = 1; i <= n; i ++) {
cout << dist[ind][i] << " ";
}
cout << endl;
}
ll distFull[MAX_N][MAX_N];
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
for(ll i = 0; i < MAX_N; i ++) {
for(ll j = 0; j < MAX_N; j ++) {
distFull[i][j] = 2400000000;
}
}
for(ll i = 0; i < MAX_N; i ++) {
distFull[i][i] = 0;
}
cin >> n >> m;
edges.resize(m);
for(ll i = 0; i < m; i ++) {
cin >> edges[i];
off[2 * i] = false;
off[2 * i + 1] = true;
g[edges[i].first.first].push_back({{edges[i].first.second, edges[i].second.first}, 2 * i});
g[edges[i].first.second].push_back({{edges[i].first.first, edges[i].second.first}, 2 * i + 1});
chkmin(distFull[edges[i].first.first][edges[i].first.second], edges[i].second.first);
}
for(ll k = 1; k <= n; k ++) {
for(ll i = 1; i <= n; i ++) {
for(ll j = 1; j <= n; j ++) {
chkmin(distFull[i][j], distFull[i][k] + distFull[k][j]);
}
}
}
dij(0, 1);
dij(1, n);
ll ret = dist[0][n] + dist[1][1];
for(ll i = 0; i < m; i ++) {
ll u = edges[i].first.first, v = edges[i].first.second, cost = edges[i].second.first, price = edges[i].second.second;
ll firstHalf = min(distFull[1][v] + cost + distFull[u][n], (ll)distFull[1][n]);
ll secondHalf = min(distFull[n][v] + cost + distFull[u][1], (ll)distFull[n][1]);
if(firstHalf + secondHalf + price > ret) {continue;}
off[2 * i] = true;
off[2 * i + 1] = false;
dij(2, 1);
dij(3, n);
chkmin(ret, price + dist[2][n] + dist[3][1]);
off[2 * i] = false;
off[2 * i + 1] = true;
}
if(ret < mod) {
cout << ret << endl;
} else {
cout << -1 << endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
896 KB |
Output is correct |
2 |
Correct |
13 ms |
768 KB |
Output is correct |
3 |
Correct |
16 ms |
896 KB |
Output is correct |
4 |
Correct |
16 ms |
768 KB |
Output is correct |
5 |
Correct |
1 ms |
768 KB |
Output is correct |
6 |
Correct |
14 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
9 |
Correct |
1 ms |
768 KB |
Output is correct |
10 |
Correct |
22 ms |
768 KB |
Output is correct |
11 |
Correct |
38 ms |
768 KB |
Output is correct |
12 |
Correct |
17 ms |
768 KB |
Output is correct |
13 |
Correct |
16 ms |
768 KB |
Output is correct |
14 |
Correct |
68 ms |
768 KB |
Output is correct |
15 |
Correct |
16 ms |
768 KB |
Output is correct |
16 |
Correct |
36 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
5888 KB |
Output is correct |
2 |
Correct |
51 ms |
5632 KB |
Output is correct |
3 |
Correct |
47 ms |
6776 KB |
Output is correct |
4 |
Correct |
16 ms |
896 KB |
Output is correct |
5 |
Correct |
15 ms |
768 KB |
Output is correct |
6 |
Correct |
14 ms |
768 KB |
Output is correct |
7 |
Correct |
14 ms |
800 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
9 |
Correct |
84 ms |
6908 KB |
Output is correct |
10 |
Correct |
66 ms |
7016 KB |
Output is correct |
11 |
Execution timed out |
1062 ms |
6912 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
768 KB |
Output is correct |
2 |
Correct |
14 ms |
768 KB |
Output is correct |
3 |
Correct |
31 ms |
4608 KB |
Output is correct |
4 |
Correct |
14 ms |
768 KB |
Output is correct |
5 |
Correct |
37 ms |
6520 KB |
Output is correct |
6 |
Correct |
1 ms |
640 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
51 ms |
6520 KB |
Output is correct |
9 |
Correct |
55 ms |
6520 KB |
Output is correct |
10 |
Execution timed out |
1093 ms |
6688 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
896 KB |
Output is correct |
2 |
Correct |
13 ms |
768 KB |
Output is correct |
3 |
Correct |
16 ms |
896 KB |
Output is correct |
4 |
Correct |
16 ms |
768 KB |
Output is correct |
5 |
Correct |
1 ms |
768 KB |
Output is correct |
6 |
Correct |
14 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
9 |
Correct |
1 ms |
768 KB |
Output is correct |
10 |
Correct |
22 ms |
768 KB |
Output is correct |
11 |
Correct |
38 ms |
768 KB |
Output is correct |
12 |
Correct |
17 ms |
768 KB |
Output is correct |
13 |
Correct |
16 ms |
768 KB |
Output is correct |
14 |
Correct |
68 ms |
768 KB |
Output is correct |
15 |
Correct |
16 ms |
768 KB |
Output is correct |
16 |
Correct |
36 ms |
768 KB |
Output is correct |
17 |
Correct |
44 ms |
5888 KB |
Output is correct |
18 |
Correct |
51 ms |
5632 KB |
Output is correct |
19 |
Correct |
47 ms |
6776 KB |
Output is correct |
20 |
Correct |
16 ms |
896 KB |
Output is correct |
21 |
Correct |
15 ms |
768 KB |
Output is correct |
22 |
Correct |
14 ms |
768 KB |
Output is correct |
23 |
Correct |
14 ms |
800 KB |
Output is correct |
24 |
Correct |
1 ms |
640 KB |
Output is correct |
25 |
Correct |
84 ms |
6908 KB |
Output is correct |
26 |
Correct |
66 ms |
7016 KB |
Output is correct |
27 |
Execution timed out |
1062 ms |
6912 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |