fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using pii = pair<int, int>;
  5. const int N = 200010;
  6. const int inf = 1e9;
  7.  
  8. vector<pii> G[N];
  9.  
  10. int main()
  11. {
  12. /**
  13.   * Input format:
  14.   * first line: n m
  15.   * each hyperedge line: num_nodes weight node1 node2 node3 ... nodelast
  16.   * last line: s t
  17.   */
  18. int n, m;
  19. scanf("%d%d", &n, &m);
  20. // construct edges in hypergraph
  21. for (int i = 0; i < m; ++i) {
  22. int c, w;
  23. scanf("%d%d", &c, &w);
  24. while (c--) {
  25. int v;
  26. scanf("%d", &v);
  27. G[v].push_back({n+i, w});
  28. G[n+i].push_back({v, 0});
  29. }
  30. }
  31. int s, t;
  32. scanf("%d%d", &s, &t);
  33.  
  34. // normal dijkstra
  35. vector<int> dist(n+m, inf);
  36. vector<bool> visited(n+m, false);
  37. dist[s] = 0;
  38. priority_queue<pii, vector<pii>, greater<pii>> Q;
  39. Q.push({dist[s], s});
  40. while (!Q.empty()) {
  41. int u = Q.top().second;
  42. Q.pop();
  43. if (visited[u])
  44. continue;
  45. visited[u] = true;
  46. if (u == t)
  47. break;
  48. for (auto vw : G[u]) {
  49. int v = vw.first, w = vw.second;
  50. if (!visited[v] && dist[u]+w < dist[v]) {
  51. dist[v] = dist[u]+w;
  52. Q.push({dist[v], v});
  53. }
  54. }
  55. }
  56. printf("%d\n", visited[t] ? dist[t] : -1);
  57.  
  58. return 0;
  59. }
Success #stdin #stdout 0s 19920KB
stdin
13 6
3 7 0 1 2
5 5 1 2 3 5 6
5 3 3 4 5 7 9
5 8 5 6 7 8 11
2 4 9 10
3 3 10 11 12
0 12
stdout
22