11015 – 05-2 Rendezvous

 

Problem Link

#Solution

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
int main()
{
char x[30][15];
int ad[30][30];
int mn,u,v,c,sum,n,m,cs=1;
while(scanf(“%d%d\n”,&n, &m) && n)
{

for(int i=1;i<=n;i++)
cin>>x[i];
for(int i=1;i<=n;i++)
{
ad[i][i]=0;
for(int j=i+1;j<=n;j++)
ad[i][j]=ad[j][i]=inf;
}

for(int i=0;i<m;i++)
{
cin>>u>>v>>c;
ad[u][v]=ad[v][u]=c;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
ad[i][j]=min(ad[i][j],ad[i][k]+ad[k][j]);
}

mn=inf;
int key=0;
for(int i=1;i<=n;i++)
{
int sum=0;
for(int j=1;j<=n;j++)
sum+=ad[i][j];

if(sum<mn)
{
mn=sum;
key=i;
}
}
printf(“Case #%d : %s\n”,cs++,x[key]);

}
return 0;
}

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in uva and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s