## 11810 - Gentle ping, to the old King

Moderator: Board moderators

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

### 11810 - Gentle ping, to the old King

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;
}``````