fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6.  
  7. struct edge{
  8. 	int dest, wt;
  9. 	char tag;
  10. };
  11.  
  12. const ll a = 137, mod = 1000000007;
  13.  
  14. vector<edge> adj[1010];
  15. string str;
  16. ll pa[10100], dist[1010];
  17. map<pair<ll, int>, ll> m1;
  18.  
  19. typedef pair<ll, pair<int, pair<ll, int> > > ds;
  20.  
  21. int main()
  22. {
  23. 	//freopen("i.txt", "r", stdin);
  24. 	int n, m, i, j, u, v, cur, z;
  25. 	char c;
  26. 	ll hash, x, y, cdist, chash, ndist, nhash, clen;
  27. 	pa[0] = 1;
  28. 	for(i=1; i<=10000; i++)
  29. 		pa[i] = (pa[i-1]*a)%mod;
  30. 	scanf("%d%d", &n, &m);
  31. 	for(i=0; i<m; i++){
  32. 		scanf("%d%d%d %c", &u, &v, &z, &c);
  33. 		adj[u].push_back((edge){v, z, c});
  34. 		adj[v].push_back((edge){u, z, c});
  35. 	}
  36. 	cin >> str;
  37. 	for(i=0; i<str.size(); i++){
  38. 		hash = 0;
  39. 		for(j=i; j<str.size(); j++){
  40. 			x = (pa[j-i]*1ll*(str[j]-'a'))%mod;
  41. 			hash = (hash+x)%mod;
  42. 			m1[make_pair(hash, j-i+1)]++;
  43. 		}
  44. 	}
  45. 	//cout << m1[make_pair(0, 1)] << "\n";
  46. 	for(i=1; i<=n; i++)
  47. 		dist[i] = INT_MAX;
  48. 	priority_queue< ds, vector< ds >, greater< ds > > pq;
  49. 	pq.push(make_pair(0, make_pair(1, make_pair(0, 0))));
  50. 	dist[0] = 0;
  51. 	while(!pq.empty()){
  52. 		cdist = pq.top().first;
  53. 		cur = pq.top().second.first;
  54. 		chash = pq.top().second.second.first;
  55. 		clen = pq.top().second.second.second;
  56. 		pq.pop();
  57. 		if(cdist>dist[cur])
  58. 			continue;
  59. 		for(i=0; i<adj[cur].size(); i++){
  60. 			x = (pa[clen]*1ll*(adj[cur][i].tag - 'a'))%mod;
  61. 			nhash = (chash+x)%mod;
  62. 			if(m1.find(make_pair(nhash, clen+1))==m1.end())
  63. 				continue;
  64. 			ndist = cdist + (m1[make_pair(nhash, clen+1)]*(adj[cur][i].wt));
  65. 			if(ndist < dist[adj[cur][i].dest]){
  66. 				dist[adj[cur][i].dest] = ndist;
  67. 				pq.push(make_pair(ndist, make_pair(adj[cur][i].dest, make_pair(nhash, clen+1))));
  68. 			}
  69. 		}
  70. 	}
  71. 	printf("%lld\n", dist[n]);
  72. 	return 0;
  73. }
Success #stdin #stdout 0s 3564KB
comments (?)
stdin
copy 
3 3
1 2 3 a
2 3 4 b
1 3 5 c
aabb
stdout
copy 
10
https://ideone.com/hXdgAz
language:
C++14 (gcc 8.3)
created:
8 years 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!