#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
struct edge{
int a,b,c,d;
};
const int mxn=405;
vector<edge>e;
vector<int>temp;
pii parent[mxn];
int id[mxn];
pair<pii,int> w[mxn][mxn];
map<pii,bool>mp;
void upd(pair<pii,int> &p,int x,int y,int z){
if(x<p.F.F){
p={{x,y},z};
}
else if(x==p.F.F and y<p.F.S){
p.F.S=y;
p.S=z;
}
}
vector<int> dij(int st,int n){
vector<int>dis(mxn);
for(int i=0;i<mxn;i++)dis[i]=1e9;
dis[st]=0;
for(int i=1;i<=n;i++){
parent[i]={-1,8e18};
}
vector<bool>used(n+1,0);
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(used[j])continue;
if(t==-1 or dis[j]<dis[t]){
t=j;
}
}
used[t]=1;
for(int j=1;j<=n;j++){
if(dis[t]+w[t][j].F.F<dis[j]){
dis[j]=dis[t]+w[t][j].F.F;
parent[j]={t,w[t][j].F.F+w[t][j].F.S};
id[j]=w[t][j].S;
}
}
}
return dis;
}
vector<int> rdij(int st,int n){
vector<int>dis(mxn);
for(int i=0;i<mxn;i++)dis[i]=1e9;
dis[st]=0;
for(int i=1;i<=n;i++){
parent[i]={-1,8e18};
}
vector<bool>used(n+1,0);
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(used[j])continue;
if(t==-1 or dis[j]<dis[t]){
t=j;
}
}
used[t]=1;
for(int j=1;j<=n;j++){
if(dis[t]+w[j][t].F.F<dis[j]){
dis[j]=dis[t]+w[j][t].F.F;
parent[j]={t,w[j][t].F.F+w[j][t].F.S};
id[j]=w[j][t].S;
}
}
}
return dis;
}
vector<int> dij2(int st,int n){
vector<int>dis(mxn);
for(int i=0;i<mxn;i++)dis[i]=1e9;
dis[st]=0;
vector<bool>used(n+1,0);
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(used[j])continue;
if(t==-1 or dis[j]<dis[t]){
t=j;
}
}
used[t]=1;
for(int j=1;j<=n;j++){
if(dis[t]+w[t][j].F.F<dis[j]){
dis[j]=dis[t]+w[t][j].F.F;
}
}
}
return dis;
}vector<int> rdij2(int st,int n){
vector<int>dis(mxn);
for(int i=0;i<mxn;i++)dis[i]=1e9;
dis[st]=0;
vector<bool>used(n+1,0);
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(used[j])continue;
if(t==-1 or dis[j]<dis[t]){
t=j;
}
}
used[t]=1;
for(int j=1;j<=n;j++){
if(dis[t]+w[j][t].F.F<dis[j]){
dis[j]=dis[t]+w[j][t].F.F;
}
}
}
return dis;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
setio();
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
parent[i]={-1,-1};
for(int j=1;j<=n;j++){
w[i][j]={{1e18,1e18},1e18};
}
}
for(int i=0;i<m;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
e.pb({a,b,c,d});
upd(w[a][b],c,d,i);
//cout<<w[a][b].S<<'\n';
}
vector<int>temp2;
temp2=dij2(n,n);
temp=dij(1,n);
int ans=temp[n]+temp2[1];
//cout<<ans<<'\n';
vector<bool>used(m+1,0);
for(int i=1;i<=n;i++){
//cout<<w[parent[i].F][]<<' ';
if(parent[i].F==-1)continue;
auto x=w[parent[i].F][i];
//if(x.F.F==1e18)continue;
used[x.S]=1;
//cout<<x.S<<' '<<i<<' '<<parent[i].F<<' '<<parent[i].S<<' ';
x=w[i][parent[i].F];
w[i][parent[i].F].F.F=min(parent[i].S,w[i][parent[i].F].F.F);
temp2=dij2(n,n);
temp=dij2(1,n);
//for(int j=1;j<=n;j++)cout<<temp[j]<<','<<temp2[j]<<' ';
// cout<<'\n';
ans=min(ans,temp[n]+temp2[1]);
w[i][parent[i].F]=x;
}
temp2=dij(1,n);
temp=rdij(n,n);
for(int i=1;i<=n;i++){
if(parent[i].F==-1)continue;
auto x=w[i][parent[i].F];
used[x.S]=1;
x=w[parent[i].F][i];
w[parent[i].F][i].F.F=min(parent[i].S,w[parent[i].F][i].F.F);
temp2=rdij2(1,n);
temp=rdij2(n,n);
ans=min(ans,temp[1]+temp2[n]);
w[parent[i].F][i]=x;
}
temp2=dij(n,n);
temp=rdij(1,n);
for(int i=1;i<=n;i++){
if(parent[i].F==-1)continue;
auto x=w[i][parent[i].F];
used[x.S]=1;
x=w[parent[i].F][i];
w[parent[i].F][i].F.F=min(parent[i].S,w[parent[i].F][i].F.F);
temp2=rdij2(n,n);
temp=rdij2(1,n);
ans=min(ans,temp[n]+temp2[1]);
w[parent[i].F][i]=x;
}
temp2=rdij(1,n);
temp=dij(n,n);
for(int i=1;i<=n;i++){
if(parent[i].F==-1)continue;
auto x=w[parent[i].F][i];
used[x.S]=1;
x=w[i][parent[i].F];
w[i][parent[i].F].F.F=min(parent[i].S,w[i][parent[i].F].F.F);
temp2=dij2(1,n);
temp=dij2(n,n);
ans=min(ans,temp[1]+temp2[n]);
w[i][parent[i].F]=x;
}
temp2=dij(n,n);
temp=dij(1,n);
for(int i=0;i<m;i++){
if(used[i])continue;
auto [a,b,c,d]=e[i];
ans=min(ans,min(temp[n],temp[b]+c+d+temp2[a])+min(temp2[1],temp2[b]+c+d+temp[a]));
//cout<<ans<<'\n';
}
if(ans>=1e9){
cout<<-1<<'\n';
return 0;
}
cout<<ans<<'\n';
}
/*
how to deal with 重邊
*/
Compilation message
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:217:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
217 | auto [a,b,c,d]=e[i];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
24 ms |
2900 KB |
Output is correct |
| 3 |
Correct |
173 ms |
2740 KB |
Output is correct |
| 4 |
Correct |
177 ms |
2740 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 6 |
Correct |
40 ms |
2652 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
204 ms |
5548 KB |
Output is correct |
| 2 |
Incorrect |
199 ms |
5336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
2736 KB |
Output is correct |
| 2 |
Correct |
64 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
168 ms |
5588 KB |
Output is correct |
| 4 |
Correct |
45 ms |
2688 KB |
Output is correct |
| 5 |
Correct |
168 ms |
5336 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
24 ms |
2900 KB |
Output is correct |
| 3 |
Correct |
173 ms |
2740 KB |
Output is correct |
| 4 |
Correct |
177 ms |
2740 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 6 |
Correct |
40 ms |
2652 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
