Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //: CCC2010S4.cpp
- #include <bits/stdc++.h>
- using namespace std;
- int dist[102];
- int dist1[102];
- struct cmp {
- bool operator() (const int& a, const int& b) {
- if(dist[a] == dist[b]) {
- return a < b;
- }
- else {
- return dist[a] < dist[b];
- }
- }
- };
- struct cmp1 {
- bool operator() (const int& a, const int& b) {
- if(dist1[a] == dist1[b]) {
- return a < b;
- }
- else {
- return dist1[a] < dist1[b];
- }
- }
- };
- int M;
- int ep;
- int corner;
- int cost;
- vector<int> v;
- pair<int, int> edges[1002][1002];
- int infinity = 1000000000;
- set<int> G[102];
- int C[102][102];
- set<int, cmp> s;
- set<int, cmp1> s1;
- int ans = 0;
- int ans1 = 0;
- int main() {
- for(int i=0; i<102; i++) {
- for(int j=0; j<102; j++) {
- C[i][j] = infinity;
- }
- }
- cin >> M;
- for(int i=1; i<=M; i++) {
- cin >> ep;
- for(int j=0; j<ep; j++) {
- cin >> corner;
- v.push_back(corner);
- }
- for(int j=0; j<ep; j++) {
- cin >> cost;
- if(edges[v[j]][v[(j+1)%ep]].first == 0) {
- edges[v[j]][v[(j+1)%ep]] = make_pair(cost, i);
- edges[v[(j+1)%ep]][v[j]] = make_pair(cost, i);
- }
- else {
- G[i].insert(edges[v[j]][v[(j+1)%ep]].second);
- G[edges[v[j]][v[(j+1)%ep]].second].insert(i);
- C[edges[v[j]][v[(j+1)%ep]].second][i] = cost;
- C[i][edges[v[j]][v[(j+1)%ep]].second] = cost;
- edges[v[j]][v[(j+1)%ep]] = make_pair(infinity, i);
- edges[v[(j+1)%ep]][v[j]] = make_pair(infinity, i);
- }
- }
- v.clear();
- }
- for(int i=0; i<1002; i++) {
- for(int j=0; j<1002; j++) {
- if(edges[i][j].first != infinity && edges[i][j].first != 0) {
- G[M+1].insert(edges[i][j].second);
- G[edges[i][j].second].insert(M);
- if(edges[i][j].first < C[M+1][edges[i][j].second]) {
- C[M+1][edges[i][j].second] = edges[i][j].first;
- C[edges[i][j].second][M+1] = edges[i][j].first;
- }
- }
- }
- }
- for(int i=1; i<M+1; i++) {
- dist[i] = infinity;
- }
- dist[1] = 0;
- s.insert(1);
- while(! s.empty()) {
- int v = *s.begin();
- s.erase(s.begin());
- for(set<int>::iterator it = G[v].begin(); it != G[v].end(); it++) {
- if(C[v][*it] < dist[*it] && *it != M+1) {
- s.erase(*it);
- dist[*it] = C[v][*it];
- s.insert(*it);
- }
- }
- }
- for(int i=1; i<=M+1; i++) {
- dist1[i] = infinity;
- }
- dist1[1] = 0;
- s1.insert(1);
- while(! s1.empty()) {
- int v = *s1.begin();
- s1.erase(s1.begin());
- for(set<int>::iterator it = G[v].begin(); it != G[v].end(); it++) {
- if(C[v][*it] < dist1[*it]) {
- s1.erase(*it);
- dist1[*it] = C[v][*it];
- s1.insert(*it);
- }
- }
- }
- for(int i=1; i<=M; i++) {
- if(dist[i] != infinity) {
- ans = ans + dist[i];
- }
- }
- for(int i=1; i<=M+1; i++) {
- if(dist1[i] != infinity) {
- ans1 = ans1 + dist1[i];
- }
- }
- ans = min(ans, ans1);
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement