#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
struct Edge{
int u, v, c, d;
Edge(){};
};
const int MAX_E = 5*1e4;
const int MAX_V = 200;
const int INF = 1e15;
int v, e;
Edge edges[MAX_E];
vector<pii> adj[MAX_V];
int find_len(int begin, int dest){
vector<int> dist(v, INF);
vector<pii> prev(v, pii(-1, -1));
dist[begin] = 0;
priority_queue<pii> pq;
pq.push(pii(0, begin));
while(pq.size()>0){
auto cur = pq.top();
pq.pop();
int u = cur.second;
int u_dist = -cur.first;
if(dist[u] == u_dist){
//cout<<u<<" "<<dist[u]<<endl;
for(auto next: adj[u]){
int next_dist = u_dist + edges[next.second].c;
if(next_dist< dist[next.first]){
dist[next.first] = next_dist;
pq.push(pii(-next_dist, next.first));
prev[next.first].first = u;
prev[next.first].second = next.second;
}
}
}
}
return dist[dest];
}
vector<int> find_path(int begin, int dest){
vector<int> dist(v, INF);
vector<pii> prev(v, pii(-1, -1));
dist[begin] = 0;
priority_queue<pii> pq;
pq.push(pii(0, begin));
while(pq.size()>0){
auto cur = pq.top();
pq.pop();
int u = cur.second;
int u_dist = -cur.first;
if(dist[u] == u_dist){
//cout<<u<<" "<<dist[u]<<endl;
for(auto next: adj[u]){
int next_dist = u_dist + edges[next.second].c;
if(next_dist< dist[next.first]){
dist[next.first] = next_dist;
pq.push(pii(-next_dist, next.first));
prev[next.first].first = u;
prev[next.first].second = next.second;
}
}
}
}
if(dist[dest] == INF){
return vector<int>(0);
}
else{
int cur = dest;
vector<int> res;
while(cur!=begin){
res.push_back(prev[cur].second);
cur = prev[cur].first;
}
return res;
}
}
int d[MAX_V][MAX_V];
bool is_path[MAX_E];
void find_d(){
for(int i = 0; i<v; i++){
for(int j = 0; j<v; j++){
d[i][j] = INF;
}
adj[i].clear();
}
for(int i = 0; i<v; i++){
d[i][i] = 0;
}
for(int i = 0; i<e; i++){
d[edges[i].u][edges[i].v] = min(d[edges[i].u][edges[i].v], edges[i].c);
adj[edges[i].u].push_back(pii(edges[i].v, i));
}
}
void floyd(){
for(int mid= 0; mid<v; mid++){
for(int f= 0; f<v; f++){
for(int l = 0; l<v; l++){
d[f][l] = min(d[f][l], d[f][mid] + d[mid][l]);
}
}
}
}
signed main(){
cin>>v>>e;
for(int i = 0; i<e; i++){
cin>>edges[i].u>>edges[i].v>>edges[i].c>>edges[i].d;
edges[i].u--;
edges[i].v--;
//adj[edges[i].u].push_back(pii(edges[i].v, i));
//d[edges[i].u][edges[i].v] = min(d[edges[i].u][edges[i].v], edges[i].c);
}
find_d();
auto p1 = find_path(0, v-1);
auto p2 = find_path(v-1, 0);
if(p1.size()>201||p2.size()>201){
return 4;
}
for(auto e : p1){
is_path[e] = true;
}
for(auto e: p2){
is_path[e] = true;
}
floyd();
int res = d[0][v-1] + d[v-1][0];
//cout<<go<<" "<<back<<endl;
for(int i = 0; i<e; i++){
//if(!is_path[i]){
int from = edges[i].v;
int to = edges[i].u;
res = min(res, min(d[0][v-1], d[0][from] + edges[i].c + d[to][v-1] ) + min(d[v-1][0], d[v-1][from] + edges[i].c + d[to][0])+ edges[i].d);
//}
}
for(int i = 0; i<e; i++){
if(is_path[i]){
swap(edges[i].u, edges[i].v);
find_d();
swap(edges[i].u, edges[i].v);
res = min(res, find_len(0, v-1) + find_len(v-1, 0) +edges[i].d);
}
}
if(res>=INF){
cout<<-1<<endl;
return 0;
}
cout<<res<<endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
576 KB |
Output is correct |
2 |
Correct |
7 ms |
596 KB |
Output is correct |
3 |
Correct |
9 ms |
596 KB |
Output is correct |
4 |
Correct |
9 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
7 ms |
636 KB |
Output is correct |
7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
50 ms |
3544 KB |
Output is correct |
2 |
Correct |
53 ms |
3536 KB |
Output is correct |
3 |
Correct |
54 ms |
3556 KB |
Output is correct |
4 |
Correct |
9 ms |
724 KB |
Output is correct |
5 |
Correct |
9 ms |
588 KB |
Output is correct |
6 |
Correct |
7 ms |
668 KB |
Output is correct |
7 |
Correct |
7 ms |
596 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
47 ms |
3404 KB |
Output is correct |
10 |
Correct |
48 ms |
4628 KB |
Output is correct |
11 |
Correct |
56 ms |
4612 KB |
Output is correct |
12 |
Correct |
55 ms |
4804 KB |
Output is correct |
13 |
Correct |
53 ms |
4672 KB |
Output is correct |
14 |
Correct |
54 ms |
4784 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
596 KB |
Output is correct |
2 |
Correct |
8 ms |
644 KB |
Output is correct |
3 |
Correct |
39 ms |
2704 KB |
Output is correct |
4 |
Correct |
7 ms |
596 KB |
Output is correct |
5 |
Correct |
46 ms |
3372 KB |
Output is correct |
6 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
576 KB |
Output is correct |
2 |
Correct |
7 ms |
596 KB |
Output is correct |
3 |
Correct |
9 ms |
596 KB |
Output is correct |
4 |
Correct |
9 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
7 ms |
636 KB |
Output is correct |
7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |