fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define endl "\n"
  4. #define F first
  5. #define S second
  6. #define loop(a,n) for(int i=a; i<=n ; i++)
  7. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  8. #define NAME "DUONGDI"
  9. using namespace std;
  10.  
  11. int a[105][105]; 
  12. int dp[105];
  13. int trace[105];
  14. string c;
  15. int n;
  16. void nhap(){
  17.     cin >> n;
  18.     for(int i = 1; i <= n-1; i++){
  19.         for(int j = 2; j <= n; j++) {
  20.             cin >> c;
  21.             if(c[0] == '-') a[i][j] = 1e9;
  22.             else a[i][j] = stoi(c);
  23.         }        
  24.     }
  25. }
  26. void solve(){
  27.     for(int i = 1; i <= n; i++) dp[i] = 1e9;
  28.         dp[1] = 0;
  29.  
  30.         for(int j = 2; j <= n; j++) {
  31.             for(int i = 1; i < j; i++) {
  32.                 if(a[i][j] < 1e9 && dp[j] > dp[i] + a[i][j]) {
  33.                     dp[j] = dp[i] + a[i][j];
  34.                     trace[j] = i;
  35.                 }
  36.             }
  37.         }
  38.     cout << dp[n] << endl;
  39. }
  40. void truyvet(){   
  41.     int path[105], k = 0, u = n;
  42.     while(u != 0) {
  43.         path[k++] = u;
  44.         u = trace[u];
  45.     }
  46.     for(int i = k - 1; i >= 0; i--) {
  47.         cout << path[i] << " ";
  48.     }
  49. }
  50. int main(){
  51.     ios_base::sync_with_stdio(0);
  52.     cin.tie(0); cout.tie(0);
  53.     freopen(NAME".INP","r",stdin);
  54.     freopen(NAME".OUT","w",stdout);
  55.     nhap();
  56.     solve();
  57.     truyvet();
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KdHa7f
language:
C++ (gcc 8.3)
created:
1 day 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!