UVa11710 - Expensive subway(最小生成树)

#include <cstdio>#include <cstring>#include <string>#include <map>#include <vector>#include <algorithm>usingnamespacestd;
constintN=405;
constintINF=0x7f7f7f7f;
structEdge{
intfrom, to, c;
};
vector<int>adjList[N];
vector<Edge>edges;
map<string, int>m;
ints, c;
intstart;
intd[N];
boolvis[N];
boolinput();
voidsolve();
voidaddEdge(intu, intv, intcost);
intmain()
{
#ifndef ONLINE_JUDGEfreopen("d:\\OJ\\uva_in.txt", "r", stdin);
#endifwhile (input()) {
solve();
    }
return0;
}
boolinput()
{
scanf("%d%d", &s, &c);
if (s==0&&c==0) returnfalse;
m.clear();
for (inti=0; i<N; i++) adjList[i].clear();
edges.clear();
for (inti=0; i<s; i++) {
charbuf[N];
scanf("%s", buf);
strings1=buf;
intsize=m.size();
m[s1] =size;
    }
for (inti=0; i<c; i++) {
charbuf1[N], buf2[N];
intprice;
scanf("%s%s%d", buf1, buf2, &price);
strings1=buf1, s2=buf2;
intu=m[s1], v=m[s2];
addEdge(u, v, price);
    }
charbuf[N];
scanf("%s", buf);
strings1=buf;
start=m[s1];
returntrue;
}
voidaddEdge(intu, intv, intcost)
{
edges.push_back((Edge){u, v, cost});
edges.push_back((Edge){v, u, cost});
adjList[u].push_back(edges.size() -2);
adjList[v].push_back(edges.size() -1);
}
voidsolve()
{
memset(vis, false, sizeof(vis));
memset(d, 0x7f, sizeof(d));
d[start] =0;
vis[start] =true;
for (size_ti=0; i<adjList[start].size(); i++) {
Edgeedge=edges[adjList[start][i]];
intu=edge.to;
intc=edge.c;
d[u] =c;
    }
boolok;
intans=0;
for (inti=0; i<s-1; i++) {
intMin=INF;
intcur;
ok=true;
for (intj=0; j<s; j++) {
if (!vis[j] &&d[j] !=INF) {
if (d[j] <Min) {
Min=d[j];
cur=j;
                }
            }
        }
if (Min==INF) {
ok=false;
break;
        }
vis[cur] =true;
ans+=Min;
for (size_tj=0; j<adjList[cur].size(); j++) {
Edgeedge=edges[adjList[cur][j]];
intv=edge.to;
intcost=edge.c;
if (!vis[v]) {
if (cost<d[v]) {
d[v] =cost;
                }
            }
        }
    }
if (!ok) {
printf("Impossible\n");
    } else {
printf("%d\n", ans);
    }
}