Advertisement
Guest User

Untitled

a guest
Dec 9th, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <utility>
  5. #include <queue>
  6.  
  7. using namespace std;
  8.  
  9. struct Edge{
  10.     long long to,w;
  11.     long long was=0,nth=0;
  12.     long long idx,from;
  13.     Edge* nxt=0;
  14.     Edge(long long id=0,long long T=0,long long W=0):to(T),w(W),idx(id){}
  15.     bool operator!=(const Edge& a)const{
  16.         return a.idx!=idx||to!=a.to;
  17.     }
  18.     void print(){
  19.         cerr<<from<<" "<<to<<"\n";
  20.     }
  21. };
  22.  
  23. bool findpath(long long from, long long to,vector<vector<Edge>>& edges,long long level,long long subl){
  24.     /*cerr<<"fp:"<<from<<" "<<to<<" "<<level<<" "<<subl<<"\n";*/
  25.     const long long N=edges.size();
  26.     queue<long long> q;
  27.     vector<long long> parent(N,-1),pi(N);
  28.     parent[from]=from;
  29.     q.push(from);
  30.     while (!q.empty()){
  31.         long long pt=q.front();
  32.         q.pop();
  33.         for (long long i=0; i!=edges[pt].size();++i){
  34.             Edge& ed=edges[pt][i];
  35.             if (parent[ed.to]==-1&&level!=ed.was/10){
  36.                 q.push(ed.to);
  37.                 parent[ed.to]=pt;
  38.                 pi[ed.to]=i;
  39.             }
  40.         }
  41.     }
  42.     if (parent[to]==-1)
  43.         return 0;
  44.     long long pt=to;long long n=0,pi0=0;
  45.     while (pt!=from){
  46.         edges[parent[pt]][pi[pt]].was=level*10+subl;
  47.         edges[parent[pt]][pi[pt]].nth=--n;
  48.         if (pt!=to)
  49.             edges[parent[pt]][pi[pt]].nxt=&edges[pt][pi0];
  50.         pi0=pi[pt];
  51.         pt=parent[pt];
  52.     }
  53.     return 1;
  54. }
  55. struct Res{long long cnt=0,val=0,A=0,B=0;};
  56. Res min(const Res& a,const Res& b){
  57.     if (a.cnt==-1)return b;
  58.     if (b.cnt==-1)return a;
  59.     if (a.val>b.val) return b;return a;
  60. }
  61. #define fi first
  62. #define se second
  63. const long long inf=1000000000000000000L;
  64.  
  65.  
  66. long long wl=0;
  67. 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){
  68.     ++wl;
  69.     pair<long long,long long> res=pair<long long,long long>(inf,inf);
  70.     const long long N=edges.size();
  71.     queue<long long> q;
  72.     q.push(from);
  73.     while (1){
  74.         while (!q.empty()){
  75.             /*cerr<<ban[idx].from<<" "<<ban[idx].to<<" "<<ban[idx].w<<"\n";*/
  76.             long long pt=q.front();
  77.             q.pop();
  78.             for (long long i=0; i!=edges[pt].size();++i){
  79.             Edge& ed=edges[pt][i];
  80.             if (to==ed.to&&ed!=ban[0]&&ed!=ban[1]){/*cerr<<"B\n";*/return res;}
  81.             /*cerr<<pt<<"->"<<ed.to<<" "<<(wparent[ed.to]!=wl)<<"&&"<<(ed!=ban[0]&&ed!=ban[1])<<"\n";*/
  82.             if (wparent[ed.to]!=wl&&ed!=ban[0]&&ed!=ban[1]){
  83.                 if (ed.was/10==level) {
  84.                     if (ed.nth>ban[ed.was%10].nth){
  85.                         if (ed.was%10!=idx)
  86.                         {/*cerr<<"C\n";*/return res;}
  87.                         wparent[ed.to]=pt;
  88.                         q.push(ban[idx].to);
  89.                         ban[idx]=ed;
  90.                     }else{
  91.                     /*cerr<<pt<<"->"<<ed.to<<"i ";*/
  92.                     wparent[ed.to]=wl;
  93.                         q.push(ed.to);
  94.                     }
  95.                 }else{
  96.                     /*cerr<<pt<<"->"<<ed.to<<"i ";*/
  97.                     wparent[ed.to]=wl;
  98.                     q.push(ed.to);
  99.                 }
  100.             }
  101.             }
  102.         }
  103.         res=min(res,pair<long long,long long>(ban[idx].w,ban[idx].idx));
  104.         q.push(ban[idx].to);
  105.         if (ban[idx].nxt==0||ban[idx].nxt->was/10!=level) {/*cerr<<"A\n";*/return res;}
  106.         ban[idx]=*ban[idx].nxt;
  107.     }
  108. }
  109. void move(queue<long long>& q,vector<vector<Edge>>& edges,long long level,Edge ban[2],vector<long long>&wparent){
  110.     ++wl;
  111.     while (!q.empty()){
  112.         long long pt=q.front();
  113.         q.pop();
  114.         for (long long i=0; i!=edges[pt].size();++i){
  115.             Edge& ed=edges[pt][i];
  116.             if (wparent[ed.to]!=wl&&ed!=ban[0]&&ed!=ban[1]){
  117.                 if (ed.was/10==level) {
  118.                     if (ed.nth>ban[ed.was%10].nth){
  119.                         q.push(ban[ed.was%10].to);
  120.                         ban[ed.was%10]=ed;
  121.                     }else{
  122.                     wparent[ed.to]=wl;
  123.                         q.push(ed.to);
  124.                     }
  125.                 }else{
  126.                     wparent[ed.to]=wl;
  127.                     q.push(ed.to);
  128.                 }
  129.             }
  130.         }
  131.     }
  132.  
  133.  
  134. }
  135. Res solve2(long long from, long long to,vector<vector<Edge>>& edges,long long level){
  136.     Edge ban[2];
  137.     ban[0].from=ban[1].from=-1;
  138.     const long long N=edges.size();
  139.     queue<long long> q;
  140.     vector<long long> parent(N,-1);
  141.     parent[from]=from;
  142.     q.push(from);
  143.     for (auto& e:edges[from]){if (e.was/10==level){ban[e.was%10]=e;}}
  144.     move(q,edges,level,ban,parent);
  145.     Res re;
  146.     re.cnt=-1;
  147.     int flag=0;
  148.     do{
  149.         --flag;
  150.         /*cerr<<ban[0].from<<" "<<ban[0].to<<"\n";*/
  151.         Res p;
  152.         p.cnt=2;
  153.         pair<long long,long long> PUFF;
  154.         Edge ban1[2];
  155.         ban1[0]=ban[0];
  156.         ban1[1]=ban[1];
  157.         PUFF=findsA(from,to,edges,level,ban1,0,parent);
  158.         auto b0=ban1[0];
  159.         p.A=PUFF.se;
  160.         p.val=PUFF.fi;
  161.         ban1[0]=ban[0];
  162.         ban1[1]=ban[1];
  163.         PUFF=findsA(from,to,edges,level,ban1,1,parent);
  164.         p.B=PUFF.se;
  165.         p.val+=PUFF.fi;
  166.         /*cerr<<p.val<<"\n";*/
  167.         q.push(ban[0].to);
  168.         q.push(ban[1].to);
  169.         ban[0]=b0;ban[1]=ban1[1];
  170.         re=min(re,p);
  171.         move(q,edges,level,ban,parent);
  172.         if (!(ban[0].nxt&&ban[1].nxt)&&flag)flag=1;
  173.     }
  174.     while (flag);
  175.     return re;
  176. }
  177. Edge bridge(long long from, long long to,vector<vector<Edge>>& edges,long long level){
  178.     const long long N=edges.size();
  179.     Edge* ban=0;
  180.     queue<long long> q;
  181.     vector<long long> parent(N,-1);
  182.     parent[from]=from;
  183.     q.push(from);
  184.     while (!q.empty()){
  185.         long long pt=q.front();
  186.         q.pop();
  187.         for (long long i=0; i!=edges[pt].size();++i){
  188.             Edge& ed=edges[pt][i];
  189.             if (parent[ed.to]==-1&&&ed!=ban){
  190.                 if (ed.was/10==level) {
  191.                     if (ban==0||ed.nth>ban->nth){
  192.                         if (ban)q.push(ban->to);
  193.                         ban=&ed;
  194.                     }else
  195.                     {
  196.                         parent[ed.to]=pt;
  197.                         q.push(ed.to);
  198.                     }
  199.                 }else{
  200.                     ///*cerr<<pt<<"->"<<ed.to<<" ";*/
  201.                     parent[ed.to]=pt;
  202.                     q.push(ed.to);
  203.                 }
  204.             }
  205.         }
  206.     }
  207.     return *ban;
  208. }
  209.  
  210.  
  211. Res solve(long long from, long long to,vector<vector<Edge>>& edges,long long level){
  212.     const long long N=edges.size();
  213.     long long cnt=0;
  214.     Res r;
  215.     pair<long long,long long> a;
  216.     for (long long i=0; i!=3;++i)cnt+=findpath(from,to,edges,level,i);
  217.     switch(cnt){
  218.         case 0:return r;
  219.         case 3:r.cnt=-1;return r;
  220.         case 2:
  221.                return solve2(from,to,edges,level);
  222.         break;
  223.         case 1:
  224.             Edge br=bridge(from,to,edges,level);
  225.             /*cerr<<br.from<<" "<<br.to<<"\n";*/
  226.             r=min(solve(from,br.from,edges,level+1),solve(br.to,to,edges,level+1));
  227.             if (r.val>br.w||r.cnt==-1){r.val=br.w; r.cnt=1; r.A=br.idx;}
  228.             return r;
  229.         break;
  230.     }
  231. }
  232.  
  233. int main(){
  234.     ios::sync_with_stdio(0);
  235.     long long N,M;
  236.     cin>>N>>M;
  237.     long long CA,CB;
  238.     cin>>CA>>CB;
  239.     vector<vector<Edge>> edges(N);
  240.     for (long long i=0; i!=M;++i){
  241.         long long a,b,c;
  242.         cin>>a>>b>>c;
  243.         --a;--b;
  244.         if (a==b) continue;
  245.         edges[a].emplace_back(Edge(i,b,c));
  246.         edges[a].back().from=a;
  247.         edges[b].emplace_back(Edge(i,a,c));
  248.         edges[b].back().from=b;
  249.     }
  250.     Res r=solve(CA-1,CB-1,edges,1);
  251.     if (r.cnt==-1)cout<<"-1\n";
  252.     if (r.cnt==0)cout<<"0\n0\n\n";
  253.     if (r.cnt==1)cout<<r.val<<"\n1\n"<<r.A+1<<"\n";
  254.     if (r.cnt==2)cout<<r.val<<"\n2\n"<<r.A+1<<" "<<r.B+1<<"\n";
  255.  
  256.    
  257. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement