Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <utility>
- #include <queue>
- using namespace std;
- struct Edge{
- long long to,w;
- long long was=0,nth=0;
- long long idx,from;
- Edge* nxt=0;
- Edge(long long id=0,long long T=0,long long W=0):to(T),w(W),idx(id){}
- bool operator!=(const Edge& a)const{
- return a.idx!=idx||to!=a.to;
- }
- void print(){
- cerr<<from<<" "<<to<<"\n";
- }
- };
- bool findpath(long long from, long long to,vector<vector<Edge>>& edges,long long level,long long subl){
- /*cerr<<"fp:"<<from<<" "<<to<<" "<<level<<" "<<subl<<"\n";*/
- const long long N=edges.size();
- queue<long long> q;
- vector<long long> parent(N,-1),pi(N);
- parent[from]=from;
- q.push(from);
- while (!q.empty()){
- long long pt=q.front();
- q.pop();
- for (long long i=0; i!=edges[pt].size();++i){
- Edge& ed=edges[pt][i];
- if (parent[ed.to]==-1&&level!=ed.was/10){
- q.push(ed.to);
- parent[ed.to]=pt;
- pi[ed.to]=i;
- }
- }
- }
- if (parent[to]==-1)
- return 0;
- long long pt=to;long long n=0,pi0=0;
- while (pt!=from){
- edges[parent[pt]][pi[pt]].was=level*10+subl;
- edges[parent[pt]][pi[pt]].nth=--n;
- if (pt!=to)
- edges[parent[pt]][pi[pt]].nxt=&edges[pt][pi0];
- pi0=pi[pt];
- pt=parent[pt];
- }
- return 1;
- }
- struct Res{long long cnt=0,val=0,A=0,B=0;};
- Res min(const Res& a,const Res& b){
- if (a.cnt==-1)return b;
- if (b.cnt==-1)return a;
- if (a.val>b.val) return b;return a;
- }
- #define fi first
- #define se second
- const long long inf=1000000000000000000L;
- long long wl=0;
- pair<long long,long long> findsA(long long from, long long to,vector<vector<Edge>> edges,long long level,Edge ban[2],long long idx,vector<long long>&wparent){
- ++wl;
- pair<long long,long long> res=pair<long long,long long>(inf,inf);
- const long long N=edges.size();
- queue<long long> q;
- q.push(from);
- while (1){
- while (!q.empty()){
- /*cerr<<ban[idx].from<<" "<<ban[idx].to<<" "<<ban[idx].w<<"\n";*/
- long long pt=q.front();
- q.pop();
- for (long long i=0; i!=edges[pt].size();++i){
- Edge& ed=edges[pt][i];
- if (to==ed.to&&ed!=ban[0]&&ed!=ban[1]){/*cerr<<"B\n";*/return res;}
- /*cerr<<pt<<"->"<<ed.to<<" "<<(wparent[ed.to]!=wl)<<"&&"<<(ed!=ban[0]&&ed!=ban[1])<<"\n";*/
- if (wparent[ed.to]!=wl&&ed!=ban[0]&&ed!=ban[1]){
- if (ed.was/10==level) {
- if (ed.nth>ban[ed.was%10].nth){
- if (ed.was%10!=idx)
- {/*cerr<<"C\n";*/return res;}
- wparent[ed.to]=pt;
- q.push(ban[idx].to);
- ban[idx]=ed;
- }else{
- /*cerr<<pt<<"->"<<ed.to<<"i ";*/
- wparent[ed.to]=wl;
- q.push(ed.to);
- }
- }else{
- /*cerr<<pt<<"->"<<ed.to<<"i ";*/
- wparent[ed.to]=wl;
- q.push(ed.to);
- }
- }
- }
- }
- res=min(res,pair<long long,long long>(ban[idx].w,ban[idx].idx));
- q.push(ban[idx].to);
- if (ban[idx].nxt==0||ban[idx].nxt->was/10!=level) {/*cerr<<"A\n";*/return res;}
- ban[idx]=*ban[idx].nxt;
- }
- }
- void move(queue<long long>& q,vector<vector<Edge>>& edges,long long level,Edge ban[2],vector<long long>&wparent){
- ++wl;
- while (!q.empty()){
- long long pt=q.front();
- q.pop();
- for (long long i=0; i!=edges[pt].size();++i){
- Edge& ed=edges[pt][i];
- if (wparent[ed.to]!=wl&&ed!=ban[0]&&ed!=ban[1]){
- if (ed.was/10==level) {
- if (ed.nth>ban[ed.was%10].nth){
- q.push(ban[ed.was%10].to);
- ban[ed.was%10]=ed;
- }else{
- wparent[ed.to]=wl;
- q.push(ed.to);
- }
- }else{
- wparent[ed.to]=wl;
- q.push(ed.to);
- }
- }
- }
- }
- }
- Res solve2(long long from, long long to,vector<vector<Edge>>& edges,long long level){
- Edge ban[2];
- ban[0].from=ban[1].from=-1;
- const long long N=edges.size();
- queue<long long> q;
- vector<long long> parent(N,-1);
- parent[from]=from;
- q.push(from);
- for (auto& e:edges[from]){if (e.was/10==level){ban[e.was%10]=e;}}
- move(q,edges,level,ban,parent);
- Res re;
- re.cnt=-1;
- int flag=0;
- do{
- --flag;
- /*cerr<<ban[0].from<<" "<<ban[0].to<<"\n";*/
- Res p;
- p.cnt=2;
- pair<long long,long long> PUFF;
- Edge ban1[2];
- ban1[0]=ban[0];
- ban1[1]=ban[1];
- PUFF=findsA(from,to,edges,level,ban1,0,parent);
- auto b0=ban1[0];
- p.A=PUFF.se;
- p.val=PUFF.fi;
- ban1[0]=ban[0];
- ban1[1]=ban[1];
- PUFF=findsA(from,to,edges,level,ban1,1,parent);
- p.B=PUFF.se;
- p.val+=PUFF.fi;
- /*cerr<<p.val<<"\n";*/
- q.push(ban[0].to);
- q.push(ban[1].to);
- ban[0]=b0;ban[1]=ban1[1];
- re=min(re,p);
- move(q,edges,level,ban,parent);
- if (!(ban[0].nxt&&ban[1].nxt)&&flag)flag=1;
- }
- while (flag);
- return re;
- }
- Edge bridge(long long from, long long to,vector<vector<Edge>>& edges,long long level){
- const long long N=edges.size();
- Edge* ban=0;
- queue<long long> q;
- vector<long long> parent(N,-1);
- parent[from]=from;
- q.push(from);
- while (!q.empty()){
- long long pt=q.front();
- q.pop();
- for (long long i=0; i!=edges[pt].size();++i){
- Edge& ed=edges[pt][i];
- if (parent[ed.to]==-1&&&ed!=ban){
- if (ed.was/10==level) {
- if (ban==0||ed.nth>ban->nth){
- if (ban)q.push(ban->to);
- ban=&ed;
- }else
- {
- parent[ed.to]=pt;
- q.push(ed.to);
- }
- }else{
- ///*cerr<<pt<<"->"<<ed.to<<" ";*/
- parent[ed.to]=pt;
- q.push(ed.to);
- }
- }
- }
- }
- return *ban;
- }
- Res solve(long long from, long long to,vector<vector<Edge>>& edges,long long level){
- const long long N=edges.size();
- long long cnt=0;
- Res r;
- pair<long long,long long> a;
- for (long long i=0; i!=3;++i)cnt+=findpath(from,to,edges,level,i);
- switch(cnt){
- case 0:return r;
- case 3:r.cnt=-1;return r;
- case 2:
- return solve2(from,to,edges,level);
- break;
- case 1:
- Edge br=bridge(from,to,edges,level);
- /*cerr<<br.from<<" "<<br.to<<"\n";*/
- r=min(solve(from,br.from,edges,level+1),solve(br.to,to,edges,level+1));
- if (r.val>br.w||r.cnt==-1){r.val=br.w; r.cnt=1; r.A=br.idx;}
- return r;
- break;
- }
- }
- int main(){
- ios::sync_with_stdio(0);
- long long N,M;
- cin>>N>>M;
- long long CA,CB;
- cin>>CA>>CB;
- vector<vector<Edge>> edges(N);
- for (long long i=0; i!=M;++i){
- long long a,b,c;
- cin>>a>>b>>c;
- --a;--b;
- if (a==b) continue;
- edges[a].emplace_back(Edge(i,b,c));
- edges[a].back().from=a;
- edges[b].emplace_back(Edge(i,a,c));
- edges[b].back().from=b;
- }
- Res r=solve(CA-1,CB-1,edges,1);
- if (r.cnt==-1)cout<<"-1\n";
- if (r.cnt==0)cout<<"0\n0\n\n";
- if (r.cnt==1)cout<<r.val<<"\n1\n"<<r.A+1<<"\n";
- if (r.cnt==2)cout<<r.val<<"\n2\n"<<r.A+1<<" "<<r.B+1<<"\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement