#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]
);
}
}
}
multiset<int>v[n][n];
for(int i=0;i<m;i++){
v[all[i].x][all[i].y].insert(all[i].c);
if(2<v[all[i].x][all[i].y].size()){
auto p=v[all[i].x][all[i].y].end();
p--;
v[all[i].x][all[i].y].erase(p);
}
}
//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";
auto p=v[x][y].find(c);
if(p!=v[x][y].end())v[x][y].erase(v[x][y].find(c));
v[y][x].insert(c);
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++){
if(v[mini][j].size()){
curd[j]=min(
curd[j],
curd[mini]+*v[mini][j].begin()
);
}
}
}
/*
for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
cerr<<"\n";
*/
if(curd[n-1]==inf){
v[y][x].erase(v[y][x].find(c));
v[x][y].insert(c);
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++){
if(v[mini][j].size()){
curd[j]=min(
curd[j],
curd[mini]+*v[mini][j].begin()
);
}
}
}
/*
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";
p=v[y][x].find(c);
if(p!=v[y][x].end()){
v[y][x].erase(v[y][x].find(c));
}
v[x][y].insert(c);
}
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 |
9 ms |
2652 KB |
Output is correct |
2 |
Correct |
24 ms |
2652 KB |
Output is correct |
3 |
Correct |
118 ms |
2900 KB |
Output is correct |
4 |
Correct |
133 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
29 ms |
2660 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
47 ms |
2568 KB |
Output is correct |
11 |
Correct |
56 ms |
2652 KB |
Output is correct |
12 |
Correct |
53 ms |
2648 KB |
Output is correct |
13 |
Correct |
116 ms |
2652 KB |
Output is correct |
14 |
Correct |
112 ms |
2700 KB |
Output is correct |
15 |
Correct |
88 ms |
2648 KB |
Output is correct |
16 |
Correct |
131 ms |
2700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
489 ms |
5936 KB |
Output is correct |
2 |
Correct |
579 ms |
5968 KB |
Output is correct |
3 |
Correct |
237 ms |
5716 KB |
Output is correct |
4 |
Correct |
71 ms |
2780 KB |
Output is correct |
5 |
Correct |
100 ms |
2720 KB |
Output is correct |
6 |
Correct |
60 ms |
2652 KB |
Output is correct |
7 |
Correct |
44 ms |
2664 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Execution timed out |
1082 ms |
7200 KB |
Time limit exceeded |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
2652 KB |
Output is correct |
2 |
Correct |
24 ms |
2652 KB |
Output is correct |
3 |
Correct |
18 ms |
5468 KB |
Output is correct |
4 |
Correct |
25 ms |
2652 KB |
Output is correct |
5 |
Correct |
22 ms |
5984 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Execution timed out |
1077 ms |
5912 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
2652 KB |
Output is correct |
2 |
Correct |
24 ms |
2652 KB |
Output is correct |
3 |
Correct |
118 ms |
2900 KB |
Output is correct |
4 |
Correct |
133 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
29 ms |
2660 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
47 ms |
2568 KB |
Output is correct |
11 |
Correct |
56 ms |
2652 KB |
Output is correct |
12 |
Correct |
53 ms |
2648 KB |
Output is correct |
13 |
Correct |
116 ms |
2652 KB |
Output is correct |
14 |
Correct |
112 ms |
2700 KB |
Output is correct |
15 |
Correct |
88 ms |
2648 KB |
Output is correct |
16 |
Correct |
131 ms |
2700 KB |
Output is correct |
17 |
Correct |
489 ms |
5936 KB |
Output is correct |
18 |
Correct |
579 ms |
5968 KB |
Output is correct |
19 |
Correct |
237 ms |
5716 KB |
Output is correct |
20 |
Correct |
71 ms |
2780 KB |
Output is correct |
21 |
Correct |
100 ms |
2720 KB |
Output is correct |
22 |
Correct |
60 ms |
2652 KB |
Output is correct |
23 |
Correct |
44 ms |
2664 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Execution timed out |
1082 ms |
7200 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |