document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. /* a764             */
  2. /* AC (66ms, 2.5MB) */
  3. #pragma warning( disable : 4996 )
  4. #include <cstdio>
  5. #include <cstring>
  6. #include <cstdint>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <tuple>
  10. #define ios_jazz ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  11.  
  12. using namespace std;
  13.  
  14. using int16 = short;
  15. using uint16 = unsigned short;
  16. using uint = unsigned int;
  17. using int64 = long long;
  18. using uint64 = unsigned long long;
  19. using pii = pair<int, int>;
  20.  
  21. /* main code */
  22. #include <climits>
  23.  
  24. constexpr int MAXN = 400;
  25. int64 dis[MAXN][MAXN], Fdis[MAXN][MAXN], ans = INT64_MAX, wi;
  26. int N, M, u, v;
  27.  
  28. int main()
  29. {
  30.     scanf("%d %d", &N, &M);
  31.  
  32.     for (int i = 1; i <= N; ++i)
  33.         for (int j = 1; j <= N; ++j)
  34.             dis[i][j] = dis[j][i] = Fdis[i][j] = Fdis[j][i] = INT_MAX;
  35.  
  36.     for (int i = 0; i < M; ++i)
  37.     {
  38.         scanf("%d %d %lld", &u, &v, &wi);
  39.         Fdis[u][v] = Fdis[v][u] = dis[u][v] = dis[v][u] = min(dis[u][v], wi);
  40.     }
  41.  
  42.     for (int k = 1; k <= N; ++k)
  43.     {
  44.         for (int i = 1; i < k; ++i)
  45.             for (int j = 1; j < i; ++j)
  46.                 ans = min(ans, Fdis[i][j] + dis[i][k] + dis[j][k]);
  47.  
  48.         for (int i = 1; i <= N; ++i)
  49.             for (int j = 1; j <= N; ++j)
  50.                 Fdis[i][j] = min(Fdis[i][j], Fdis[i][k] + Fdis[k][j]);
  51.     }
  52.     if (ans == INT64_MAX)
  53.         puts("No solution.");
  54.     else
  55.         printf("%lld", ans);
  56.  
  57.     return 0;
  58. }
');