11810 - Gentle ping, to the old King

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
wazaaaap
New poster
Posts: 7
Joined: Thu Sep 23, 2010 12:55 am

11810 - Gentle ping, to the old King

Post by wazaaaap »

What's wrong with my code ? Any tricky case ?

Code: Select all

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

#define maxn 16
#define inf 1000

using namespace std;

struct edge {
    int v, w;
    edge () {}
    edge (int _v, int _w) : v(_v), w(_w) {}
};

int t, n, m, w, e, a, b, c, r, res, cost[maxn];
bool finish[maxn];

int calcShortestPath (int start, int end, vector <vector <edge> > &v) {
    for (int j=0; j < n; j++)
        cost[j] = inf;
    cost[start] = 0;
    queue <int> q;
    q.push (start);
    int tmp = start;
    finish[tmp] = false;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        finish[u] = false;
        for (int i=0; i < v[u].size(); i++) {
            int tmp_cost = cost[u] + v[u][i].w;
            if (tmp_cost >= cost[v[u][i].v]) continue;
            cost[v[u][i].v] = tmp_cost;
            if (!finish[v[u][i].v]) {
                q.push (v[u][i].v);
                finish[v[u][i].v] = true;
            }
        }
    }
    return cost[end];
}

int main() {
    char h;
    scanf ("%d", &t);
    for (int k=0; k < t; k++) {
        r = 0, res = 0;
        scanf ("%c", &h);
        scanf ("%d %d %d", &n, &m, &w);
        vector <vector <edge> > v(n);
        vector <int> pr;
        for (int j=0; j < w; j++) {
            scanf ("%d", &e);
            pr.push_back (e);
        }
        for (int l=0; l < m; l++) {
            scanf ("%d %d %d", &a, &b, &c);
            v[a].push_back (edge (b, c));
            v[b].push_back (edge (a, c));
        }
        for (int i=0; i < w; i++) {
            for (int l=0; l < n; l++) {
                if (pr[i] != l) {
                    r += calcShortestPath (pr[i], l, v);
                }
            }
            res += r;
            r = 0;
        }
        printf ("Case %d: %d\n", k+1, res);
    }
    return 0;
}

Post Reply

Return to “Volume 118 (11800-11899)”