fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  3. #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
  4. #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
  5. #define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
  6. #define ALL(v) (v).begin(), (v).end()
  7. #define IS_INF(x)   (std::isinf(x))
  8. #define IS_NAN(x)   (std::isnan(x))
  9. #define fi   first
  10. #define se   second
  11. #define MASK(i) (1LL << (i))
  12. #define BIT(x, i) (((x) >> (i)) & 1)
  13. #define div   ___div
  14. #define next   ___next
  15. #define prev   ___prev
  16. #define left   ___left
  17. #define right   ___right
  18. #define __builtin_popcount __builtin_popcountll
  19. using namespace std;
  20. template<class X, class Y>
  21.     bool minimize(X &x, const Y &y) {
  22.         X eps = 1e-9;
  23.         if (x > y + eps) {
  24.             x = y;
  25.             return true;
  26.         } else return false;
  27.     }
  28. template<class X, class Y>
  29.     bool maximize(X &x, const Y &y) {
  30.         X eps = 1e-9;
  31.         if (x + eps < y) {
  32.             x = y;
  33.             return true;
  34.         } else return false;
  35.     }
  36. template<class T>
  37.     T Abs(const T &x) {
  38.         return (x < 0 ? -x : x);
  39.     }
  40.  
  41. /* Author: Van Hanh Pham */
  42.  
  43. /** END OF TEMPLATE. DRINK A CUP OF TIGERSUGAR BEFORE READING MY CODE. **/
  44.  
  45. #define MAX   555
  46. const int INF = (int)1e9 + 7;
  47. const long long LL_INF = (long long)1e18 + 7LL;
  48.  
  49. int numNode, numEdge, numQuery;
  50. long long dist[MAX][MAX];
  51. int trace[MAX][MAX], cost[MAX][MAX];
  52. int roots[MAX], numRoot;
  53.  
  54. void loadGraph(void) {
  55.     scanf("%d%d%d", &numNode, &numEdge, &numQuery);
  56.  
  57.     memset(cost, 0x3f, sizeof cost);
  58.     REP(love, numEdge) {
  59.         int u, v, c; scanf("%d%d%d", &u, &v, &c);
  60.         minimize(cost[u][v], c);
  61.         minimize(cost[v][u], c);
  62.     }
  63. }
  64.  
  65. void floyd(void) {
  66.     memset(dist, 0x3f, sizeof dist);
  67.     FOR(i, 1, numNode) FOR(j, 1, numNode) if (cost[i][j] < INF) dist[i][j] = cost[i][j];
  68.     FOR(i, 1, numNode) dist[i][i] = 0;
  69.     FOR(k, 1, numNode) FOR(i, 1, numNode) FOR(j, 1, numNode)
  70.         minimize(dist[i][j], dist[i][k] + dist[k][j]);
  71.  
  72.     FOR(from, 1, numNode) FOR(to, 1, numNode) if (from != to) {
  73.         trace[from][to] = -1;
  74.         FOR(par, 1, numNode) if (par != to && dist[from][par] + cost[par][to] == dist[from][to])
  75.             if (trace[from][to] < 0 || cost[trace[from][to]][to] > cost[par][to]) trace[from][to] = par;
  76.     }
  77. }
  78.  
  79. void query(void) {
  80.     scanf("%d", &numRoot);
  81.     FOR(i, 1, numRoot) scanf("%d", &roots[i]);
  82.  
  83.     long long result = 0;
  84.     FOR(node, 1, numNode) {
  85.         long long bestDist = LL_INF;
  86.         FOR(i, 1, numRoot) minimize(bestDist, dist[roots[i]][node]);
  87.         if (bestDist == 0) continue;
  88.  
  89.         int minCost = INF;
  90.         FOR(i, 1, numRoot) if (bestDist == dist[roots[i]][node]) {
  91.             int par = trace[roots[i]][node];
  92.             assert(par > 0);
  93.             minimize(minCost, cost[par][node]);
  94.         }
  95.         result += minCost;
  96.     }
  97.  
  98.     printf("%lld ", result);
  99. }
  100.  
  101. void process(void) {
  102.     REP(love, numQuery) query();
  103.     printf("\n");
  104. }
  105.  
  106. int main(void) {
  107. #ifdef ONLINE_JUDGE
  108.     freopen("giaohang.inp", "r", stdin);
  109.     freopen("giaohang.out", "w", stdout);
  110. #endif // ONLINE_JUDGE
  111.     loadGraph();
  112.     floyd();
  113.     process();
  114.     return 0;
  115. }
  116.  
  117. /*** BUBBLE TEA IS GREAT. MY CODE IS AMAZING :D ***/
Success #stdin #stdout 0.01s 8384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wtXO5E
language:
C++14 (gcc 8.3)
created:
2 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!