#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=205;
const int M=50050;
const int inf=1e9+7;
struct Edge{int u,v,c,d;};
Edge edges[M];
bool bridge[M];
struct Bridges{
static const int NSZ=205;
vector<pair<int,int>> E[NSZ];
vector<int> ans;
int n,disc[NSZ],low[NSZ],tid;
void init(int _n){n=_n;tid=0;ans.clear();for(int i=1;i<=n;i++)E[i].clear(),disc[i]=low[i]=0;}
void AddEdge(int u,int v,int e){E[u].pb({v,e});E[v].pb({u,e});}
void DFS(int u,int p){
disc[u]=low[u]=++tid;
for(auto e:E[u])if(e.second!=p){
int v=e.first;
if(!disc[v]){
DFS(v,e.second);
if(low[v]>disc[u])ans.pb(e.second);
low[u]=min(low[u],low[v]);
}else low[u]=min(low[u],disc[v]);
}
}
}GPH;
void FindBridges(vector<pair<int,int>> go[],int st,int n){
GPH.init(n);
function<void(int)> CNS=[&](int u){
for(auto e:go[u]){
GPH.AddEdge(u,e.first,e.second);
CNS(e.first);
}
};
CNS(st);
GPH.DFS(st,-1);
//printf(":D\n");
for(int i:GPH.ans)bridge[i]=1;
}
void Dijkstra(vector<pair<int,int>> E[],int n,int st,int dist[],vector<pair<int,int>> go[]){
for(int i=1;i<=n;i++)dist[i]=inf,go[i].clear();
priority_queue<pair<int,int>> pq;
dist[st]=0;pq.push({0,st});
while(pq.size()){
int u=pq.top().second;
int d=-pq.top().first;
pq.pop();
if(dist[u]!=d)continue;
for(auto e:E[u]){
int v=e.first,w=edges[e.second].c;
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
go[v].clear();
pq.push({-dist[v],v});
}
if(dist[v]==dist[u]+w)go[v].pb({u,e.second});
}
}
}
vector<pair<int,int>> E[N],R[N],T[N],go[N];
void BuildRev(int j,int m,int n){
for(int i=1;i<=n;i++)T[i].clear();
for(int i=1;i<=m;i++){
if(i!=j)T[edges[i].u].pb({edges[i].v,i});
else T[edges[i].v].pb({edges[i].u,i});
}
}
int dist[2][2][N],tmp[N];
int main(){
int n,m;
scanf("%i %i",&n,&m);
for(int i=1;i<=m;i++){
scanf("%i %i %i %i",&edges[i].u,&edges[i].v,&edges[i].c,&edges[i].d);
E[edges[i].u].pb({edges[i].v,i});
R[edges[i].v].pb({edges[i].u,i});
}
Dijkstra(E,n,1,dist[0][0],go);
FindBridges(go,n,n);
Dijkstra(R,n,n,dist[0][1],go);
Dijkstra(E,n,n,dist[1][0],go);
FindBridges(go,1,n);
Dijkstra(R,n,1,dist[1][1],go);
ll ans=2*inf;
for(int i=1;i<=m;i++){
//if(bridge[i]){
BuildRev(i,m,n);
Dijkstra(T,n,1,tmp,go);
ll now=tmp[n];
//printf("%i ",tmp[n]);
Dijkstra(T,n,n,tmp,go);
now+=tmp[1];
//printf("%i ",tmp[1]);
now+=edges[i].d;
ans=min(ans,now);
//printf("%i %lld\n",i,now);
/*}else{
int u=edges[i].u,v=edges[i].v,c=edges[i].c,d=edges[i].d;
ll d1=dist[0][0][n];
if(dist[0][0][v]<dist[0][0][u])d1=min(d1,(ll)dist[0][0][v]+c+dist[0][1][u]);
ll d2=dist[1][0][1];
if(dist[1][0][v]<dist[1][0][u])d2=min(d2,(ll)dist[1][0][v]+c+dist[1][1][u]);
ans=min(ans,d1+d2+d);
}*/
}
if(ans<2*inf)printf("%lld\n",ans);
else printf("-1\n");
return 0;
}
Compilation message
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&n,&m);
~~~~~^~~~~~~~~~~~~~~
ho_t4.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i %i %i",&edges[i].u,&edges[i].v,&edges[i].c,&edges[i].d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
262 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1095 ms |
2936 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
225 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
262 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
