fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <map>
  5. #include <climits>
  6. using namespace std;
  7.  
  8. vector<long long> djkestra(map<long long, map<long long,long long> >& Map,long long n,long long i)
  9. {
  10. 	vector<long long> dp(n,LLONG_MAX);
  11. 	dp[i]=0;
  12. 	priority_queue<long long> pq;
  13. 	pq.push(i);
  14.  
  15. 	while(!pq.empty())
  16. 	{
  17. 		long long x = pq.top();
  18. 		pq.pop();
  19.  
  20. 		for(auto it=Map[x].begin();it!=Map[x].end();it++)
  21. 		{
  22. 			if(dp[x] != LLONG_MAX && dp[it->first] > dp[x] + it->second)
  23. 			{
  24. 				dp[it->first] = dp[x] + it->second;
  25. 				pq.push(it->first);
  26. 			}
  27. 		}
  28. 	}
  29.  
  30. 	return dp;
  31. }
  32.  
  33.  
  34. int main() {
  35.  
  36. 	long long n,m;
  37. 	cin>>n>>m;
  38.  
  39. 	map<long long, map<long long,long long> > Map1;
  40. 	map<long long, map<long long,long long> > Map2;
  41.  
  42. 	for(long long i=0;i<m;i++)
  43. 	{
  44. 		long long a,b,c;
  45. 		cin>>a>>b>>c;
  46. 		Map1[a-1][b-1]=c;
  47. 		Map2[b-1][a-1]=c;
  48. 	}
  49.  
  50. 	vector<long long> dist = djkestra(Map1,n,0);
  51. 	vector<long long> dist_rev = djkestra(Map2,n,n-1);
  52.  
  53. 	long long ans = LLONG_MAX;
  54. 	for(long long i=0;i<n;i++)
  55. 	{
  56. 		for(auto it=Map1[i].begin();it!=Map1[i].end();it++)
  57. 		{
  58. 			long long st = i;
  59. 			long long ed = it->first;
  60.  
  61. 			if(dist[st] != LLONG_MAX && dist_rev[ed] != LLONG_MAX)
  62. 			ans = min(ans,dist[st]+dist_rev[ed]+it->second/2);
  63. 		}
  64. 	}
  65.  
  66. 	cout<<ans<<endl;
  67.  
  68. 	return 0;
  69. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
3 4
1 2 3
2 3 1
1 3 7
2 1 5
stdout
copy 
2
https://ideone.com/Js66yr
language:
C++14 (gcc 8.3)
created:
5 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!