fork download
copy 
  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
comments (?)
stdin
copy 
4 4
4 1 5
3 4 -1
2 3 -1
1 2 -1
stdout
copy 
d[0]=0
d[1]=1
d[2]=2
d[3]=3
-1
https://ideone.com/MamINs
language:
C++14 (gcc 8.3)
created:
7 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!