OJ Board

Code: Select all

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <cstring>
#include <climits>
#include <iostream>
#include <sstream>
#include <string>
#include <numeric>
#include <utility>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
using namespace std;

#define OFF ios::sync_with_stdio(false)
#define IOR(x) freopen(x,"r",stdin);
#define IOW(x) freopen(x,"w",stdout);
#define DEBUG if(0)

#define i64 long long
#define u64 unsigned long long
#define eps 1e-10

#define LET(x,p) __typeof(p) x
#define FORIT(it,p) for(__typeof(p.end()) it=p.begin();it!=p.end();it++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ALL(p) p.begin(),p.end()
#define CLR(p) p.clear()
#define REV(p) reverse(All(p))
#define pb(p) push_back(p)
#define pii pair< int, int >
#define mset(p,v) memset(p,v,sizeof(p))
#define UB(p,v) upper_bound(ALL(p),v)
#define LB(p,v) lower_bound(ALL(p),v)
#define MAXN	2000000000
typedef pair<long,long> ii;

vector<vector<long> > adj(402,vector<long>(402,0));
vector<long> deg(402);
vector<vector<long> > cost(402,vector<long>(402,0));
vector<long> distanc(402);
map<string,long> M;
string str,str1,str2;
long c,V,E,cnt;

long Prim(long start)
{
	long dist,i,cst=0;
	ii top;
	distanc[start]=0;
	priority_queue<ii,vector<ii>,greater<ii> > Q;
	Q.push(ii(0,start));

	cnt=0;
	while(!Q.empty())
	{
		top=Q.top();
		Q.pop();
		start=top.second;
		dist=top.first;
		if(dist<=distanc[start])
		{
			cnt++;
			for(i=1;i<=deg[start];i++)
			{
				if(distanc[adj[start][i]] > cost[start][i])
				{
					distanc[adj[start][i]] = cost[start][i];
					Q.push(ii(distanc[adj[start][i]],adj[start][i]));
				}
			}
		}
	}
	for(i=1;i<=V;i++)
		cst+=distanc[i];
	return cst;
}

void Ini()
{
	long i;
	for(i=0;i<=V;i++)
		distanc[i]=MAXN;
}

int main()
{
	long i,n,c,cst,st;
    while(cin>>V>>E)
	{
		if(!V&&!E)	break;
		n=1;
		for(i=0;i<V;i++)
		{
			cin>>str;
			M[str]=n++;
		}
		for(i=0;i<E;i++)
		{
			cin>>str1>>str2>>c;
			deg[M[str1]]++;
			deg[M[str2]]++;
			adj[M[str1]][deg[M[str1]]]=M[str2];
			adj[M[str2]][deg[M[str2]]]=M[str1];
			cost[M[str1]][deg[M[str1]]]=c;
			cost[M[str2]][deg[M[str2]]]=c;
		}
		cin>>str;
		st=M[str];
		Ini();
		cst=Prim(st);
		if(cnt==V)
			cout<<cst<<endl;
		else
			cout<<"Impossible\n";
		M.clear();
		deg.clear();
	}
    return 0;
}

Code: Select all

Code Removed

Code: Select all

while(scanf("%ld%ld",&N,&M),N!=0,M!=0)

Code: Select all

2 0
a
b
a
0 0

Code: Select all

1 0
a
a
2 0
a
b
a
0 0

Code: Select all

0
Impossible