#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;
}
int u=n-1;
while(u!=0){
ll mi=MAX;
int id=-1,i2=-1;
for(auto &v:G[u]){
if(!bri[v]){
int y=otro(v,u);
if(mi>dis[y]){
mi=dis[y];
if(v!=m-1) id=v;
else i2=v;
}
}
}
if(id==-1 && i2==-1) break;
if(id==-1) u=i2;
else
u=id;
}
res=dis[n-1];
if(u!=0) 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
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 |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
2 ms |
588 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
2 ms |
588 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
2 ms |
588 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
2 ms |
588 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
354 ms |
764 KB |
Output is correct |
10 |
Correct |
375 ms |
756 KB |
Output is correct |
11 |
Correct |
256 ms |
716 KB |
Output is correct |
12 |
Correct |
256 ms |
756 KB |
Output is correct |
13 |
Correct |
166 ms |
716 KB |
Output is correct |
14 |
Correct |
169 ms |
716 KB |
Output is correct |
15 |
Correct |
175 ms |
716 KB |
Output is correct |
16 |
Correct |
173 ms |
720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
483 ms |
28268 KB |
Output is correct |
2 |
Correct |
492 ms |
28320 KB |
Output is correct |
3 |
Correct |
483 ms |
27924 KB |
Output is correct |
4 |
Correct |
485 ms |
27944 KB |
Output is correct |
5 |
Correct |
479 ms |
28200 KB |
Output is correct |
6 |
Correct |
483 ms |
28676 KB |
Output is correct |
7 |
Correct |
486 ms |
28616 KB |
Output is correct |
8 |
Correct |
501 ms |
28796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
494 ms |
28780 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
404 ms |
52016 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
404 ms |
52016 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
2 ms |
588 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
2 ms |
588 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
354 ms |
764 KB |
Output is correct |
10 |
Correct |
375 ms |
756 KB |
Output is correct |
11 |
Correct |
256 ms |
716 KB |
Output is correct |
12 |
Correct |
256 ms |
756 KB |
Output is correct |
13 |
Correct |
166 ms |
716 KB |
Output is correct |
14 |
Correct |
169 ms |
716 KB |
Output is correct |
15 |
Correct |
175 ms |
716 KB |
Output is correct |
16 |
Correct |
173 ms |
720 KB |
Output is correct |
17 |
Correct |
483 ms |
28268 KB |
Output is correct |
18 |
Correct |
492 ms |
28320 KB |
Output is correct |
19 |
Correct |
483 ms |
27924 KB |
Output is correct |
20 |
Correct |
485 ms |
27944 KB |
Output is correct |
21 |
Correct |
479 ms |
28200 KB |
Output is correct |
22 |
Correct |
483 ms |
28676 KB |
Output is correct |
23 |
Correct |
486 ms |
28616 KB |
Output is correct |
24 |
Correct |
501 ms |
28796 KB |
Output is correct |
25 |
Incorrect |
494 ms |
28780 KB |
Output isn't correct |
26 |
Halted |
0 ms |
0 KB |
- |