fork(3) download
copy 
  1. /*__ _(_) __ _  ___  ___ _   _  __| | __ _ _   _| |_ ___
  2.  / _` | |/ _` |/ _ \/ __| | | |/ _` |/ _` | | | | __/ _ \
  3. | (_| | | (_| | (_) \__ \ |_| | (_| | (_| | |_| | || (_) |
  4.  \__, |_|\__,_|\___/|___/\__,_|\__,_|\__,_|\__,_|\__\___/
  5.  |___/                                  Accepted Code  */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. int main()
  10. {
  11.     int T;
  12.     for (scanf("%d",&T); T--;)
  13.     {
  14.         int N, M, C;
  15.         int next[222][222], w[222][222];
  16.         memset(next,0,sizeof(next));
  17.         scanf("%d%d%d",&N,&M,&C);
  18.         for (int i=1; i<=M; i++)
  19.         {
  20.             int x,y,l;
  21.             scanf("%d%d%d",&x,&y,&l); // Biểu diễn đồ thì bàng danh sách kề
  22.             next[x][++next[x][0]]=y; // next[x][0] là số đỉnh kề với đỉnh x
  23.             next[y][++next[y][0]]=x; // next[x][i] là các đỉnh kề với x (0<=i<=next[x][0])
  24.             w[x][y]=w[y][x]=l; // Độ dài đường đi nối giữa x,y và y,x
  25.         }
  26.  
  27.         bool visited[222];
  28.         memset(visited,false,sizeof(visited));
  29.         int dp[222];
  30.         for(int i=0; i<222; i++) dp[i]=INT_MAX;
  31.  
  32.         dp[N]=0;
  33.         while (true)
  34.         {
  35.             int u=1; // tìm nơi cần ít nước nhất, ban đầu giả sử là 1
  36.             for(int i=2; i<=N; i++)
  37.                 if(visited[i]==false && dp[u]>dp[i]) u=i;
  38.             visited[u]=true; // đánh dấu đỉnh này đã thăm
  39.             if(u==1) break; // Khi đã về đến 1 thì dừng lại
  40.             for(int i=1; i<=next[u][0]; i++)
  41.             {
  42.                 int v=next[u][i]; // đỉnh kề với đỉnh u
  43.                 if(visited[v])continue; // nếu đã thăm rồi thì bỏ qua
  44.                 int need=dp[u]; // lượng nước cần mang tới đỉnh u
  45.                 int L=w[u][v]; // Độ dài đoạn đường nối từ u đến v
  46.                 int water; // Lượng nước mà đỉnh v tối thiểu cần có
  47.                 if(need+L<=C) water=need+L;
  48.                 else
  49.                 {
  50.                     if(C<=2*L)continue; //Nếu không đủ sức mang nước đi và về thì coi như không có cạnh nối đỉnh u và v
  51.                     int t=(need+L-C)/(C-2*L); //Số luợt đi và về
  52.                     if((need+L-C)%(C-2*L)>0) t++;
  53.                     water=(2*t+1)*L+need;
  54.                 }
  55.                 dp[v]=min(dp[v],water); //Tối ưu lại lượng nước tối thiểu cần dùng ở đỉnh v
  56.             }
  57.         }
  58.         printf("%d\n",dp[1]);
  59.     }
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0s 3724KB
comments (?)
stdin
copy 
1
9 10 25 
1 2 3 
2 3 12 
3 4 4 
3 5 9 
4 9 13 
5 9 5 
2 6 10 
6 7 10 
7 8 10 
8 9 10
stdout
copy 
65
https://ideone.com/n8m6rk
NK05DSRT - Sa mạc
language:
C++14 (gcc 8.3)
created:
9 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!