#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
const int lim=2e5+5;
#else
const int lim=3e3+3;
#endif
#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define pb push_back
const int mod=1e9+7;
//const int mod=(1ll<<61)-1;
using pii=pair<int,int>;
struct edge{
int x,y,c,d;
};
template <>
struct std::hash<pii>{
size_t operator()(const pii& k) const{
int first=hash<int>()(k.first),second=hash<int>()(k.second);
return hash<int>()(first^second);
}
};
const int inf=INT_MAX*200ll;
inline void solve(){
int n,m;
cin>>n>>m;
edge all[m];
for(int i=0;i<m;i++){
cin>>all[i].x>>all[i].y>>all[i].c>>all[i].d;
all[i].x--,all[i].y--;
}
int dist[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
dist[i][j]=inf;
}
}
for(int i=0;i<m;i++){
dist[all[i].x][all[i].y]=min(
all[i].c,
dist[all[i].x][all[i].y]
);
}
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
dist[i][j]=min(
dist[i][j],
dist[i][k]+dist[k][j]
);
}
}
}
pii v[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
v[i][j]={inf,inf};
}
}
for(auto[x,y,c,d]:all){
if(c<v[x][y].second){
v[x][y].second=c;
if(v[x][y].second<v[x][y].first){
swap(v[x][y].first,v[x][y].second);
}
}
}
/*
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cerr<<(v[i][j].first^inf?v[i][j].first:-1)<<" "<<(v[i][j].second^inf?v[i][j].second:-1)<<" | ";
}cerr<<"\n";
}
*/
//cerr<<"ok\n";
int ans=dist[0][n-1]+dist[n-1][0];
//cerr<<ans<<"\n";
for(auto[x,y,c,d]:all){
//cerr<<"\n"<<x<<" "<<y<<" "<<c<<" "<<dist[y][x]<<"\n";
if(dist[y][x]<=c)continue;
//cerr<<dist[y][x]-c<<" "<<(dist[0][n-1]+dist[n-1][0])-ans<<"\n";
pii p1=v[x][y],p2=v[y][x];
if(v[x][y].first==c){
swap(v[x][y].first,v[x][y].second);
}
if(c<v[y][x].second){
v[y][x].second=c;
if(v[y][x].second<v[y][x].first){
swap(v[y][x].first,v[y][x].second);
}
}
/*
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cerr<<(v[i][j].first^inf?v[i][j].first:-1)<<" | ";
}cerr<<"\n";
}
*/
int curd[n];
for(int i=0;i<n;i++){
curd[i]=inf;
}
curd[0]=0;
bool vis[n];
memset(vis,0,sizeof(vis));
for(int i=0;i<n-1;i++){
int mini=-1;
for(int j=0;j<n;j++){
if(!vis[j]&&(~mini?(curd[j]<curd[mini]):1)){
mini=j;
}
}
vis[mini]=1;
if(mini==n-1)break;
for(int j=0;j<n;j++){
curd[j]=min(
curd[j],
curd[mini]+v[mini][j].first
);
}
}
/*
for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
cerr<<"\n";
*/
if(curd[n-1]==inf){
v[x][y]=p1;
v[y][x]=p2;
continue;
}
int ansnow=curd[n-1];
for(int i=0;i<n;i++){
curd[i]=inf;
}
curd[n-1]=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<n-1;i++){
int mini=-1;
for(int j=0;j<n;j++){
if(!vis[j]&&(~mini?(curd[j]<curd[mini]):1)){
mini=j;
}
}
vis[mini]=1;
if(!mini)break;
for(int j=0;j<n;j++){
curd[j]=min(
curd[j],
curd[mini]+v[mini][j].first
);
}
}
/*
for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
cerr<<"\n";
*/
if(curd[0]!=inf){
ansnow+=curd[0]+d;
ans=min(ans,ansnow);
}
//cerr<<ansnow<<"\n\n";
v[x][y]=p1;
v[y][x]=p2;
}
if(ans<inf-100)cout<<ans<<"\n";
else cout<<"-1\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
#ifdef Local
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#else
#endif
int t=1;
//cin>>t;
while (t--)
{
solve();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
1368 KB |
Output is correct |
2 |
Correct |
24 ms |
1372 KB |
Output is correct |
3 |
Correct |
109 ms |
1372 KB |
Output is correct |
4 |
Correct |
120 ms |
1368 KB |
Output is correct |
5 |
Correct |
2 ms |
856 KB |
Output is correct |
6 |
Correct |
27 ms |
1372 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
43 ms |
1420 KB |
Output is correct |
11 |
Correct |
48 ms |
1368 KB |
Output is correct |
12 |
Correct |
49 ms |
1372 KB |
Output is correct |
13 |
Correct |
109 ms |
1372 KB |
Output is correct |
14 |
Correct |
103 ms |
1400 KB |
Output is correct |
15 |
Correct |
80 ms |
1404 KB |
Output is correct |
16 |
Correct |
117 ms |
1396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
214 ms |
2932 KB |
Output is correct |
2 |
Correct |
269 ms |
2784 KB |
Output is correct |
3 |
Correct |
177 ms |
2908 KB |
Output is correct |
4 |
Correct |
66 ms |
1372 KB |
Output is correct |
5 |
Correct |
95 ms |
1404 KB |
Output is correct |
6 |
Correct |
60 ms |
1372 KB |
Output is correct |
7 |
Correct |
41 ms |
1372 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Execution timed out |
1091 ms |
2908 KB |
Time limit exceeded |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
1372 KB |
Output is correct |
2 |
Correct |
22 ms |
1372 KB |
Output is correct |
3 |
Correct |
15 ms |
2392 KB |
Output is correct |
4 |
Correct |
24 ms |
1368 KB |
Output is correct |
5 |
Correct |
18 ms |
2908 KB |
Output is correct |
6 |
Correct |
1 ms |
600 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Execution timed out |
1058 ms |
2908 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
1368 KB |
Output is correct |
2 |
Correct |
24 ms |
1372 KB |
Output is correct |
3 |
Correct |
109 ms |
1372 KB |
Output is correct |
4 |
Correct |
120 ms |
1368 KB |
Output is correct |
5 |
Correct |
2 ms |
856 KB |
Output is correct |
6 |
Correct |
27 ms |
1372 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
43 ms |
1420 KB |
Output is correct |
11 |
Correct |
48 ms |
1368 KB |
Output is correct |
12 |
Correct |
49 ms |
1372 KB |
Output is correct |
13 |
Correct |
109 ms |
1372 KB |
Output is correct |
14 |
Correct |
103 ms |
1400 KB |
Output is correct |
15 |
Correct |
80 ms |
1404 KB |
Output is correct |
16 |
Correct |
117 ms |
1396 KB |
Output is correct |
17 |
Correct |
214 ms |
2932 KB |
Output is correct |
18 |
Correct |
269 ms |
2784 KB |
Output is correct |
19 |
Correct |
177 ms |
2908 KB |
Output is correct |
20 |
Correct |
66 ms |
1372 KB |
Output is correct |
21 |
Correct |
95 ms |
1404 KB |
Output is correct |
22 |
Correct |
60 ms |
1372 KB |
Output is correct |
23 |
Correct |
41 ms |
1372 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Execution timed out |
1091 ms |
2908 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |