1031. Campus

TAG 最短路 Dijkstra

经典题目，直接用Dijkstra就行，只是注意要把字符串映射成编号，我用STL的map容器做的。还有节点数最多是200

/* source code of submission 424628, Zhongshan University Online Judge System */
#include <stdio.h>
#include <map>
#include <string>
#include <memory.h>
using namespace std;
char s1[110],s2[110];
int  g[200][200];
int  t,n;
int  idx1,idx2,len;
int  counter;
map<string,int> node;
int  findIndex( char *s )
{
    if ( node.count(s)==0 )
    {
        ++counter;
        node[s]=counter;
        return counter; 
    }
    else
    {
        return node[s];
    }
}
int Dijkstra(int s,int t)
{
    int dist[200];
    bool visited[200];
    
    if (s==t)
    return 0;
    
    memset(visited, false, sizeof(visited) );
    memset(dist, -1, sizeof(dist) );
    dist[s]=0;
    visited[s]=true;
    for (int i=0; i<=counter; ++i)
    {
        if ( i!=s )
        {
            dist[i]=g[s][i];
        }
    }
    for (int k=1; k<=counter; ++k)
    {
        int mind=90000;
        int idx=-1;
        for (int i=0; i<=counter; ++i)
        {
            if ( !visited[i] && dist[i]!=-1 && dist[i]<mind )
            {
                mind=dist[i];
                idx=i;
            }
        }
        visited[idx]=true;
        if ( idx==t )
        {
            return dist[t];
        }
        for (int i=0; i<=counter; ++i)
        {
            if ( !visited[i] && g[idx][i]!=-1 )
            {
                if (dist[i]==-1 || dist[i]> dist[idx]+g[idx][i]  )
                {
                    dist[i]=dist[idx]+g[idx][i];
                }                
            }
        }
    }
    
    return -1;
}
int main(int argc, char *argv[])
{
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%d", &n);
        node.clear();
        counter=-1;
        memset(g, -1, sizeof(g) );
        for (int i=0; i<n; ++i)
        {
            scanf("%s%s%d", s1, s2, &len );
            idx1=findIndex(s1);
            idx2=findIndex(s2);
            g[idx1][idx2]=len;
            g[idx2][idx1]=len;
        }
        scanf("%s%s",s1, s2);
        printf("%d/n",  Dijkstra( findIndex(s1), findIndex(s2) ) );
    }
    return 0;
}