제출 #36104

#제출 시각아이디문제언어결과실행 시간메모리
36104mohammad_kilani통행료 (APIO13_toll)C++14
16 / 100
1219 ms3292 KiB
#include <bits/stdc++.h> using namespace std; #define mod 1000000007 #define oo 2000000000 const int N = 1010; int n , m , k , prnt[N] , cur[N]; long long current = 0 , comp[N]; vector< pair< pair<int,int> , pair<int,int> > > v,ed2; vector< vector< pair<int, pair<int,int> > > > g; pair<int,int> ed[30]; int Find(int u){ if(u == prnt[u]) return u; return prnt[u] = Find(prnt[u]); } void min_tree(vector< pair< pair<int,int> ,pair<int,int> > > v, vector < vector< pair<int, pair<int,int> > > > &g,bool b){ g.clear(); g.resize(n+1); sort(v.begin(),v.end()); for(int i=1;i<=n;i++) prnt[i] = i; for(int i=0;i<v.size();i++){ int a = Find(prnt[v[i].second.first]); int b = Find(prnt[v[i].second.second]); if(a == b) continue; prnt[a] = b; g[v[i].second.first].push_back(make_pair(v[i].second.second,v[i].first)); g[v[i].second.second].push_back(make_pair(v[i].second.first,v[i].first)); if(b) ed2.push_back(v[i]); } } void DFS2(int node,int prnt,int num){ comp[node] = num; for(int i=0;i<g[node].size();i++){ if(g[node][i].first != prnt) DFS2(g[node][i].first,node,num); } } long long get(int node,int node2){ DFS2(node,node2,1); long long mn = oo; for(int i=0;i<ed2.size();i++){ if(ed2[i].first.first == 0) continue; if(comp[ed2[i].second.first] == comp[ed2[i].second.second]) continue; mn = min(mn,(long long)ed2[i].first.first); } DFS2(node,node2,0); return mn; } long long DFS(int node,int prnt){ long long all = 0 ; for(int i=0;i<g[node].size();i++){ if(g[node][i].first == prnt) continue; long long res = DFS(g[node][i].first,node); if(g[node][i].second.second){ current += res * get(node,g[node][i].first); } all += res; } return all + cur[node]; } int main() { //freopen("in.txt","r",stdin); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) prnt[i] = i ; for(int i=0;i<m;i++){ int u ,V , c; scanf("%d%d%d",&u,&V,&c); v.push_back(make_pair(make_pair(c,0),make_pair(u,V))); } min_tree(v,g,1); for(int i=0;i<k;i++){ scanf("%d%d",&ed[i].first,&ed[i].second); } for(int i=1;i<=n;i++) scanf("%d",&cur[i]); long long ans = 0 ; for(int i=0;i<(1 << k);i++){ for(int j=0;j<k;j++){ if((i >> j & 1) == 1) ed2.push_back(make_pair(make_pair(0,1),ed[j])); } min_tree(ed2,g,0); current = 0 ; DFS(1,-1); ans = max(ans,current); for(int j=0;j<k;j++){ if((i >> j & 1) == 1) ed2.pop_back(); } } cout << ans << endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

toll.cpp: In function 'void min_tree(std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >, std::vector<std::vector<std::pair<int, std::pair<int, int> > > >&, bool)':
toll.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++){
               ^
toll.cpp: In function 'void DFS2(int, int, int)':
toll.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
               ^
toll.cpp: In function 'long long int get(int, int)':
toll.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ed2.size();i++){
               ^
toll.cpp: In function 'long long int DFS(int, int)':
toll.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
               ^
toll.cpp: In function 'int main()':
toll.cpp:68:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&k);
                          ^
toll.cpp:72:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&u,&V,&c);
                           ^
toll.cpp:77:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&ed[i].first,&ed[i].second);
                                           ^
toll.cpp:80:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&cur[i]);
                      ^
#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...