Submission #891038

#TimeUsernameProblemLanguageResultExecution timeMemory
891038Sir_Ahmed_ImranTraining (IOI07_training)C++17
10 / 100
3 ms604 KiB
///~~~LOTA~~~/// #include <bits/stdc++.h> using namespace std; #define nl '\n' #define ff first #define ss second #define ll long long #define append push_back #define pii pair<int,int> #define all(x) (x).begin(),(x).end() #define N 1001 int dp[N]; int dept[N]; vector<int> a[N]; void dfs(int v,int u){ dept[v]=dept[u]+1; for(auto& i:a[v]) if(i!=u) dfs(i,v); } void solve(){ int n,m,o,p,q,r; cin>>n>>m; vector<pair<pii,int>> v,u; for(int i=o=0;i<m;i++){ cin>>p>>q>>r; if(!r){ a[p].append(q); a[q].append(p); } else v.append({{p,q},r}); o+=r; } for(int i=1;i<=n;i++){ if(a[i].size()==1){ dfs(i,0); break; } } for(auto& i:v) u.append({{max(dept[i.ff.ff],dept[i.ff.ss]) ,min(dept[i.ff.ff],dept[i.ff.ss])},i.ss}); sort(all(u)); for(auto& i:u) for(int j=0;j<=i.ff.ss;j++) dp[i.ff.ff]=max(dp[i.ff.ff],dp[j]+i.ss); for(int i=r=0;i<=n;i++) r=max(r,dp[i]); cout<<o-r; } int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...