This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> ii;
typedef vector<int> vi;
const int MAX_N=3e5+10;
const ll MAX=1e15;
ll ma[MAX_N];
ll dis[MAX_N];
vector<vi> G;
vector<ll> a,b,w;
int n,m;
bool pri[MAX_N];
bool bri[MAX_N],vis[MAX_N];
int num[MAX_N],low[MAX_N];
int it=0;
int otro(int id,int x){
if(a[id]==x) return b[id];
else return a[id];
}
void bridge(int u,int p){
num[u]=low[u]=it++;
vis[u]=1;
for(auto &v:G[u]){
int y;
if(u==a[v]) y=b[v];
else y=a[v];
if(!vis[y]){
bridge(y,u);
if(low[y]>num[u]){
bri[v]=1;
}
low[u]=min(low[u],low[y]);
}
else
if(y!=p)
low[u]=min(low[u],num[v]);
}
}
vector<ii> bfs(int u){
for(int i=0;i<n;i++) dis[i]=MAX;
dis[u]=0;
priority_queue<ii, vector<ii>, greater<ii> > pq;
pq.push(ii(0,u));
while(!pq.empty()){
int x=pq.top().second;
int k=pq.top().first;
pq.pop();
for(auto &v:G[x]){
int y;
if(x==a[v]) y=b[v];
else y=a[v];
if(dis[y]>dis[x]+w[v]){
dis[y]=dis[x]+w[v];
pq.push(ii(dis[y],y));
}
}
}
memset(pri,0,sizeof pri);
vector<ii> path;
int st,en;
if(u==0){
en=0; st=n-1;
}
else{
st=0; en=n-1;
}
u=st;
while(u!=en){
int id=-1;
ll mi=MAX;
for(auto &v:G[u]){
int y;
if(u==a[v]) y=b[v];
else y=a[v];
if(mi>dis[y]){
id=v; mi=dis[y];
}
}
if(u==a[id]) u=b[id];
else u=a[id];
path.push_back(ii(u,id));
}
reverse(path.begin(),path.end());
return path;
}
int main(){
cin>>n>>m;
G.resize(n+1);
bool sw=0;
for(int i=0;i<m;i++){
int x,y,z; cin>>x>>y>>z;
x--; y--;
if(z!=1) sw=1;
a.push_back(x);
b.push_back(y);
w.push_back(z);
G[x].push_back(i);
G[y].push_back(i);
}
ma[m]=0;
for(int i=m-1;i>=0;i--)
ma[i]=max(ma[i+1],w[i+1]);
ll res=0;
vector<ii> path=bfs(0);
if(m==n-1){
for(int i=0;i<path.size();i++){
int id=path[i].second;
if(id==m-1) continue;
ll rp=dis[n-1]+ma[id];
res=max(res,rp);
}
}
else{
if(m==n || !sw){
if(!sw){
memset(bri,0,sizeof bri);
for(int i=0;i<path.size();i++){
if(path[i].second!=m-1)
bri[path[i].second]=1;
}
ll d[MAX_N];
for(int i=0;i<n;i++) d[i]=MAX;
d[0]=0;
queue<int> q;
q.push(0);
while(!q.empty()){
int x=q.front();
q.pop();
for(auto &v:G[x]){
int y=otro(v,x);
if(d[y]>d[x]+1){
d[y]=d[x]+1;
q.push(y);
}
}
}
res=dis[n-1];
if(dis[n-1]!=d[n-1]) res++;
}
else{
}
}
else{
for(int i=0;i<m-1;i++){
w[i]+=ma[i];
bfs(0);
res=max(res,dis[n-1]);
w[i]-=ma[i];
}
}
}
cout<<res<<endl;
}
Compilation message (stderr)
Aesthetic.cpp: In function 'std::vector<std::pair<long long int, int> > bfs(int)':
Aesthetic.cpp:47:9: warning: unused variable 'k' [-Wunused-variable]
47 | int k=pq.top().first;
| ^
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:107:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i=0;i<path.size();i++){
| ~^~~~~~~~~~~~
Aesthetic.cpp:118:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int i=0;i<path.size();i++){
| ~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |