OJ Board

Code: Select all

3 1
Hector
John
Ray
2 3 1

Code: Select all

Case #1 : John

Code: Select all

int main(void)
{
    int N,M,I,J,K,**graph,*dist,*d,min,ans,cas=0;
    char **name;
    while(cin>>N>>M)
    {
        cas++;
        if(!N)
            break;
        graph = new int*[N];
        for(int i=0;i<N;i++)
            graph[i] = new int[N];
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                graph[i][j] = 0;
        dist = new int[N];
        for(int i=0;i<N;i++)
            dist[i] = 0;
        name = new char*[N];
        for(int i=0;i<N;i++)
        {
            name[i] = new char[11];
            cin>>name[i];
        }
        for(int i=0;i<M;i++)
        {
            cin>>I>>J>>K;
            graph[I-1][J-1] = graph[J-1][I-1] = K;
        }
        for(int i=0;i<N;i++)
        {
            d = min_dist(N,graph,i);
            for(int j=0;j<N;j++)
                dist[j] += d[j];
        }
        min = dist[0];
        ans = 0;
        for(int i=1;i<N;i++)
        {
            if(dist[i]<min)
            {
                ans = i;
                min = dist[i];
            }
        }
        cout<<"Case #"<<cas<<" : "<<name[ans]<<endl;
        for(int i=0;i<N;i++)
        {
            delete graph[i];
            delete name[i];
        }
        delete graph;
        delete name;
    }
    return 0;
}

Code: Select all

int* min_dist(int N,int** graph,int k)

Code: Select all

        for(int i=0;i<N;i++)
        {
            d = min_dist(N,graph,i);
            for(int j=0;j<N;j++)
                dist[j] += d[j];
        } 

Code: Select all

/*
ID:mhayter1
PROG:ride
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <cctype>
#include <cstdio>
#include <iomanip>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;

/*
ifstream fin(".in");
ofstream fout(".out");
*/

const int INFINITY=1010;

int main()
{
    int distance[30][30];
    int n,m;
    string array[30];
    for(int cases=1;cin>>n>>m;cases++)
    {
        if(n==0 && m==0)
            break;
        for(int i=0;i<25;i++)
        {
            for(int j=0;j<25;j++)
            {
                distance[i][j]=INFINITY;
            }
        }
        for(int i=0;i<n;i++)
        {
            cin>>array[i+1];
        }
        int u,v,w;
        for(int i=0;i<m;i++)
        {
            cin>>u>>v>>w;
            distance[u][v]=distance[v][u]=w;
        }
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(distance[i][k]+distance[k][j]<distance[i][j])
                    {
                        distance[i][j]=distance[i][k]+distance[k][j];
                    }
                }
            }
        }
        int minsum=23*INFINITY;
        int cursum=0;
        int where=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cursum+=distance[i][j];
            }
            if(cursum<minsum)
            {
                minsum=cursum;
                where=i;
            }
            cursum=0;
        }
        cout<<"Case #"<<cases<<" : "<<array[where]<<endl;
    }
    int y;
    cin>>y;
    return 0;
}

Code: Select all

int dijkstra(const int dis[22][22], const int& m, const int& start_p)
{
    int dis_min[m];          //  minimun distance
    bool not_vis[m];         //  haven't visited
    
    fill(dis_min, dis_min+m, DIS_MAX);
    fill(not_vis, not_vis+m, true);
    dis_min[start_p] = 0;
    
    for(int j = 0; j < m; j++)
    {
        int ptr = -1, min = DIS_MAX;
        
        for(int i = 0; i < m; i++)
            if((not_vis[i] == true)&&(min > dis_min[i]))
                min = dis_min[i], ptr = i;
        
        if(ptr == -1)
            break;
        
        for(int i = 0; i < m; i++)
            if(dis_min[ptr] + dis[ptr][i] < dis_min[i])
                dis_min[i] = dis_min[ptr] + dis[ptr][i];
        
        not_vis[ptr] = false;
    }
    
    int sum = 0;
    
    for(int i = 0; i < m; i++)
        sum += dis_min[i];
    
    return sum;              //  the shortest path start from start_p
}