fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4. #include <map>
  5. using namespace std;
  6.  
  7. struct node
  8. {
  9. long long a,b,x;
  10. node(long long a1,long long b1,long long x1)
  11. {
  12. a=a1;
  13. b=b1;
  14. x=x1;
  15. }
  16. };
  17.  
  18. void dfs(map<long long ,map<long long,long long> >& Map,vector<long long>& visited,int i)
  19. {
  20. visited[i]=1;
  21. for(auto it=Map[i].begin();it!=Map[i].end();it++)
  22. {
  23. if(visited[it->first] == 0)
  24. {
  25. dfs(Map,visited,it->first);
  26. }
  27. }
  28. }
  29.  
  30. int main() {
  31.  
  32. long long n,m;
  33. cin>>n>>m;
  34. vector<node*> edges;
  35. map<long long ,map<long long,long long> > Map1;
  36. map<long long ,map<long long,long long> > Map2;
  37. vector<long long> vis1(n,0);
  38. vector<long long> vis2(n,0);
  39. for(long long i=0;i<m;i++)
  40. {
  41. long long a,b,x;
  42. cin>>a>>b>>x;
  43. edges.push_back(new node(a-1,b-1,-1*x));
  44. Map1[a-1][b-1]=1;
  45. Map2[b-1][a-1]=1;
  46. }
  47.  
  48. dfs(Map1,vis1,0);
  49. dfs(Map2,vis2,n-1);
  50.  
  51. long long d[n];
  52. for(long long i=0;i<m;i++)
  53. {
  54. d[i] = LLONG_MAX;
  55. }
  56. d[0]=0;
  57. for(long long i=0;i<n-1;i++)
  58. {
  59. for(long long j=0;j<edges.size();j++)
  60. {
  61. long long u = edges[j]->a;
  62. long long v = edges[j]->b;
  63. long long w = edges[j]->x;
  64.  
  65. if(d[u] != LLONG_MAX && d[v] > d[u]+w)
  66. {
  67. d[v] = d[u]+w;
  68. }
  69. }
  70. }
  71.  
  72. for(long long i=0;i<n;i++)
  73. {
  74. cout<<"d["<<i<<"]="<<d[i]<<endl;
  75. }
  76.  
  77. long long flag=0;
  78. for(long long j=0;j<edges.size();j++)
  79. {
  80. long long u = edges[j]->a;
  81. long long v = edges[j]->b;
  82. long long w = edges[j]->x;
  83.  
  84. if(d[v] > d[u]+w && vis1[v] && vis2[v])
  85. {
  86. cout<<-1<<endl;
  87. return 0;
  88. }
  89. }
  90.  
  91. cout<<d[n-1]*-1<<endl;
  92.  
  93. return 0;
  94. }
Success #stdin #stdout 0.01s 5284KB
stdin
4 4
4 1 5
3 4 -1
2 3 -1
1 2 -1
stdout
d[0]=0
d[1]=1
d[2]=2
d[3]=3
-1