fork download
copy 
  1. /******************
  2.    TESTER CODE
  3.  
  4.     **OPTIMAL**
  5.  
  6. Problem- DP Made Easy
  7. Tester- spj_29
  8. Complexity- nlog(n)
  9.  
  10. *******************/
  11.  
  12. #include <bits/stdc++.h>
  13.  
  14. using namespace std;
  15.  
  16. #define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  17. #define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
  18. #define ll long long int
  19. #define FF first
  20. #define SS second
  21. #define mp make_pair
  22. #define pb push_back
  23. #define pii pair<int,int>
  24. #define pll pair<long long int,long long int>
  25. #define sd(x) scanf("%d",&x)
  26. #define slld(x) scanf("%lld",&x)
  27. #define pd(x) printf("%d\n",x)
  28. #define plld(x) printf("%lld\n",x)
  29. #define pss printf
  30. #define MOD 1000000007
  31. #define INF 1e18
  32. #define eps 0.00001
  33. #define endl '\n'
  34. #define debug(n1) cout<<n1<<endl
  35. ll n,m,q,fsum[100005];
  36. vector<vector<pll>>adj;
  37. vector<ll>d,d1,tmp;
  38. set<pll>s;
  39. multiset<ll>b;
  40. vector<ll>dij(vector<vector<pll>>g,ll src)
  41. {
  42. 	s.clear();
  43. 	tmp.clear();
  44. 	tmp.resize(n+5,INF);
  45. 	s.insert(mp(0,src));
  46. 	tmp[src]=0;
  47. 	while(!s.empty())
  48. 	{
  49. 		ll i=s.begin()->SS;
  50. 		ll x=s.begin()->FF;
  51. 		s.erase(s.begin());
  52. 		for(auto j:g[i])
  53. 			if(tmp[j.FF]>j.SS+x)
  54. 			{
  55. 				auto h=s.find(mp(tmp[j.FF],j.FF));
  56. 				if(h!=s.end())
  57. 					s.erase(h);
  58. 				tmp[j.FF]=j.SS+x;
  59. 				s.insert(mp(tmp[j.FF],j.FF));
  60. 			}
  61. 	}
  62. 	return tmp;
  63. }
  64. int main() {
  65. SPEED;
  66. cin>>n>>m>>q;
  67. adj.resize(n+5);
  68. d.resize(n+1,INF);
  69. d1.resize(n+1,INF);
  70. tmp.resize(n+1);
  71. for(int i=1;i<=m;i++)
  72. {
  73. 	ll x,y,w;
  74. 	cin>>x>>y>>w;
  75. 	adj[x].pb(mp(y,w));
  76. 	adj[y].pb(mp(x,w));
  77. }
  78. d=dij(adj,1);
  79. d1=dij(adj,n);
  80. for(int i=1;i<=n;i++)
  81. {
  82. 	ll x,y,z;
  83. 	cin>>x>>y>>z;
  84. 	fsum[i]=x+y+z;
  85. 	b.insert(d[i]+d1[i]+(x+y+z)*(n-1));
  86. }
  87. for(int i=1;i<=q;i++)
  88. {
  89. 	ll j,x,y,z;
  90. 	cin>>j>>x>>y>>z;
  91. 	b.erase(b.find(d[j]+d1[j]+fsum[j]*(n-1)));
  92. 	fsum[j]=x+y+z;
  93. 	b.insert(d[j]+d1[j]+fsum[j]*(n-1));
  94. 	cout<<*b.begin()<<endl;
  95. }
  96. 	return 0;
  97.            }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
2 1 2
2 1 5
1 1 1
5 4 1
2 2 2 1
1 3 2 2
stdout
copy 
8
10
https://ideone.com/nOXdaX
language:
C++14 (clang 8.0)
created:
6 years ago
visibility:
secret

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!