fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     ios_base::sync_with_stdio(0),cin.tie(0);
  5.     int n,m,i,i2,a,b,c;
  6.     char s;
  7.     vector<int>v,v2,v1,v4,vd;
  8.     //v1 la stack muitipurpuse
  9.     //v la working time
  10.     //v4 la longest last node -1 if none -2 if more than 2
  11.     //vd distance
  12.     //v2 la requerment
  13.     vector<vector<array<int,2>>>v3;
  14.     while(cin>>n>>m){
  15.         v.resize(1);
  16.         v2.resize(0);
  17.         v3.resize(0);
  18.         v4.resize(0);
  19.         vd.resize(0);
  20.         v2.resize(n,0);
  21.         v3.resize(n);
  22.         v4.resize(n,-1);
  23.         vd.resize(n,0);
  24.         cin>>v[0];
  25.         for(i=n;--i;)cin>>s>>i2,v.push_back(i2);
  26.         while(m--){
  27.             cin>>a>>b>>c;
  28.             v2[b]++;
  29.             v3[a].push_back({b,c});
  30.         }
  31.         for(i=n;i--;){
  32.             for(v1.push_back(i);!v1.empty();){
  33.                 i2=v1.back();
  34.                 v1.pop_back();
  35.                 if(!v2[i2]--){//neu cac node truoc da xong
  36.                     vd[i2]+=v[i2];
  37.                     for(auto i:v3[i2]){
  38.                         if(vd[i[0]]<(i[1]+=vd[i2])){
  39.                             v4[i[0]]=(v4[i2]==-2?-2:i2);
  40.                             vd[i[0]]=i[1];
  41.                         }else if(vd[i[0]]==i[1])v4[i[0]]=-2;
  42.                         v1.push_back(i[0]);
  43.                     }
  44.                 }
  45.             }
  46.         }
  47.         i=max_element(vd.begin(),vd.end())-vd.begin();
  48.         cout<<vd[i];
  49.         if(v4[i]!=-2 and count(vd.begin(),vd.end(),vd[i])){
  50.             for(v1.push_back(i);v1.back()!=-1;v1.push_back(v4[v1.back()]));
  51.             v1.pop_back();
  52.             while(!v1.empty()){
  53.                 cout<<","<<v1.back();
  54.                 v1.pop_back();
  55.             }
  56.             cout<<"\n";
  57.         }else cout<<",M\n";
  58.     }
  59. }
  60.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
6 7
10 ,8 ,9 ,10 ,11 ,12
0 1 1
1 2 2
1 3 3
1 4 4
2 5 5
3 5 6
4 5 7
6 7
10 ,8 ,9 ,11 ,11 ,12
0 1 1
1 2 2
1 3 4
1 4 4
2 5 5
3 5 7
4 5 7
8 11
2 ,7 ,2 ,6 ,5 ,1 ,2 ,7
6 7 2
0 1 4
0 2 2
1 3 6
1 4 5
1 5 3
2 4 1
3 6 2
3 7 9
4 5 2
5 7 2
stdout
copy 
53,0,1,4,5
53,M
41,0,1,3,7
https://ideone.com/Yut4xT
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!