#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=205, INF=1e16, G=1e6;
vector<int> all[N][N], all2[N][N];
vector<vector<int>> a, b, c, d;
vector<vector<array<int, 3>>> g(N), g_rev(N);
queue<int> pq[G];
vector<int> dijkstra_rev(int v, int skip){
vector<int> dist(N, INF);
dist[v] = 0;
pq[0].push(v);
int q=0;
while(q<G){
if(!pq[q].size()) q++;
else{
int v=pq[q].front(); pq[q].pop();
if(v==skip||dist[v] != q) continue;
for(auto [i, l, j]: g_rev[v]){
if(dist[i] > q+l){
dist[i] = q+l;
pq[dist[i]].push(i);
}
}
}
}
return dist;
}
vector<int> dijkstra(int v, int skip){
vector<int> dist(N, INF);
dist[v]=0;
pq[0].push(v);
int q=0;
while(q<G){
if(!pq[q].size()) q++;
else{
int v=pq[q].front(); pq[q].pop();
if(v==skip||dist[v] != q) continue;
for(auto [i, l, j]: g[v]){
if(dist[i] > q+l){
dist[i] = q+l;
pq[dist[i]].push(i);
}
}
}
}
return dist;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m; cin >> n >> m;
vector<array<int, 3>> e(m);
vector<int> di(m);
int cnt =0;
for(auto &[u, v, c]: e){
cin >> u >> v >> c >> di[cnt];
u--; v--;
g[u].push_back({v, c, cnt});
g_rev[v].push_back({u, c, cnt});
all[u][v].push_back(cnt);
all2[u][v].push_back(cnt);
cnt++;
}
for(int i=0; i<n; i++){
sort(g[i].begin(), g[i].end(), [&](auto x, auto y){
return x[1] < y[1];
});
sort(g_rev[i].begin(), g_rev[i].end(), [&](auto x, auto y){
return x[1] < y[1];
});
for(int l=0; l<n; l++){
sort(all[i][l].begin(), all[i][l].end(), [&](int x, int y){
return e[x][2] < e[y][2];
});
sort(all2[i][l].begin(), all2[i][l].end(), [&](int x, int y){
return e[x][2]+di[x] < e[y][2]+di[y];
});
}
}
// a = 1 -> i, b = i -> n
// c = i -> 1 without x
// d = n -> i without x
for(int i=0; i<=n; i++){
a.push_back(dijkstra(0, i));
b.push_back(dijkstra_rev(n-1, i));
c.push_back(dijkstra_rev(0, i));
d.push_back(dijkstra(n-1, i));
}
int ans=INF;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(i==j) continue;
if(a[j][i]==INF||b[i][j]==INF) continue;
int sum=a[j][i]+b[i][j];
int tsum=sum, ksum=INF;
int g=0;
for(auto k: all2[j][i]){
g++;
if(g==3) break;
sum=tsum;
sum+=e[k][2];
sum+=di[k];
if(all[j][i].size()>1){
if(k==all[j][i][0])
ans=min(ans, sum+d[i][j]+c[j][i]+e[all[j][i][1]][2]);
else
ans=min(ans, sum+d[i][j]+c[j][i]+e[all[j][i][0]][2]);
}
ans=min(ans, sum+c[i][j]+d[j][i]+e[k][2]);
// diğer değer
if(all[i][j].size()>0){
ans=min(ans, sum+c[i][j]+d[j][i]+e[all[i][j][0]][2]);
}
ksum=min(ksum, sum);
}
for(int g=0; g<n; g++){
if(g!=i&&g!=j){
ans=min(ans, ksum+d[j][g]+c[i][g]);
ans=min(ans, ksum+d[i][g]+c[j][g]);
}
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
//blocklanan edge i ve j arasında
if(i==j) continue;
if(d[j][i]==INF||c[i][j]==INF) continue;
int sum=d[j][i]+c[i][j];
int tsum=sum, ksum=INF;;
int g=0;
for(auto k: all2[j][i]){
g++;
if(g==3) break;
sum=tsum;
sum+=e[k][2];
sum+=di[k];
if(all[j][i].size()>1){
if(k==all[j][i][0])
ans=min(ans, sum+b[j][i]+a[i][j]+e[all[j][i][1]][2]);
else
ans=min(ans, sum+b[j][i]+a[i][j]+e[all[j][i][0]][2]);
}
ans=min(ans, sum+a[j][i]+b[i][j]+e[k][2]);
if(all[i][j].size()>0){
ans=min(ans, sum+a[j][i]+b[i][j]+e[all[i][j][0]][2]);
}
ksum=min(ksum, sum);
}
for(int g=0; g<n; g++){
if(g!=i&&g!=j){
ans=min(ans, ksum+b[j][g]+a[i][g]);
ans=min(ans, ksum+b[i][g]+a[j][g]);
}
}
}
}
ans = min(ans, a[n][n-1]+d[n][0]);
if(ans==INF) cout<<-1;
else cout<<ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
113 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
104 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
111 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
113 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
