fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define FastIO ios::sync_with_stdio(false)
  5. #define read freopen("in.in","r",stdin)
  6. #define write freopen("out.out","w",stdout)
  7. typedef long long ll;
  8. const int N = 2e5 + 5;
  9. const int MOD = 1e9 + 7;
  10. typedef pair<ll, ll> ii;
  11. typedef long long ll;
  12. double ebs = 1e-9;
  13. vector<vector<pair<int, char>>>adjlist;
  14. int vis[N], level[N], parent[N];
  15. string lex[N];
  16. struct Compare {
  17. 	bool operator()(pair<string, int> const& p1, pair<string, int> const& p2)
  18. 	{
  19. 		if (p1.first.length() == p2.first.length())
  20. 			return p1.first > p2.first;
  21. 		return p1.first.length() > p2.first.length();
  22. 	}
  23. };
  24. void bfs(int source, int dis) {
  25. 	vis[source] = 1;
  26. 	level[source] = 0;
  27. 	lex[source] = "";
  28. 	priority_queue< pair<string, int>, vector<pair<string, int>>, Compare>q;
  29. 	q.push(make_pair("", source));
  30. 	while (!q.empty()) {
  31. 		int node = q.top().second;
  32. 		q.pop();
  33.  
  34. 		if (node == dis)break;
  35. 		for (int i = 0; i < adjlist[node].size(); i++)
  36. 		{
  37. 			int child = adjlist[node][i].first;
  38. 			if (!vis[child]) {
  39. 				parent[child] = node;
  40. 				level[child] = level[node] + 1;
  41. 				lex[child] = lex[node] + adjlist[node][i].second;
  42. 				vis[child] = 1;
  43. 				q.push(make_pair(lex[child], child));
  44. 			}
  45. 		}
  46. 	}
  47. }
  48. void print(int dis) {
  49. 	vector<int>res;
  50. 	int node = dis;
  51. 	while (node != -1) {
  52. 		res.push_back(node);
  53. 		node = parent[node];
  54. 	}
  55. 	if (res[0] == dis && res[res.size() - 1] == 1) {
  56. 		for (int i = res.size() - 1; i >= 0; i--)
  57. 			cout << res[i] << " ";
  58. 		cout << endl;
  59. 	}
  60. 	else
  61. 		cout << -1 << endl;
  62. }
  63. int main() {
  64. 	FastIO;
  65. #ifndef ONLINE_JUDGE
  66. 	write; read;
  67. #endif 
  68. 	int n, m; cin >> n >> m;
  69. 	adjlist.resize(n + 1);
  70. 	memset(parent, -1, sizeof parent);
  71. 	memset(vis, 0, sizeof vis);
  72. 	memset(level, 0, sizeof level);
  73. 	for (int i = 0; i < n; i++)
  74. 		lex[i] = "";
  75. 	int a, b;
  76. 	char c;
  77. 	for (int i = 0; i < m; i++)
  78. 	{
  79. 		cin >> a >> b >> c;
  80. 		adjlist[a].push_back({ b,c });
  81. 		adjlist[b].push_back({ a,c });
  82. 	}
  83. 	bfs(1, n);
  84. 	cout << level[n] << endl;
  85. 	print(n);
  86. 	cout << lex[n] << endl;
  87.  
  88. }
Success #stdin #stdout 0.01s 12284KB
comments (?)
stdin
copy 
4 4
1 2 b
2 4 a
1 3 a
3 4 z
stdout
copy 
2
1 3 4 
az
https://ideone.com/9pSJUu
language:
C++14 (gcc 8.3)
created:
5 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!