2112.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<stdio.h>
#include<string>
const int maxint=0x7fffffff;
int  v,u,w,t;
int  length[180][151],dist[180];
char start[40],end[40];
char way[180][40],temp1[40],temp2[40];
bool s[180];
int main()
{
    int n,ca,i,j,k;
    while(scanf("%d",&n)==1){
        if(n==-1)   break;
        memset(length,0,sizeof(length));
        memset(dist,0,sizeof(dist));
        memset(start,0,sizeof(start));
        memset(end,0,sizeof(end));
        memset(way,0,sizeof(way));
        memset(temp1,0,sizeof(temp1));
        memset(temp2,0,sizeof(temp2));
        int c=0;
        scanf("%s%s",start,end);
        if(n==0){
            if(strcmp(start,end)==0)
                printf("0\n");
            else
                printf("-1\n");
            continue;
        }
        strcpy(way[c++],start);
        strcpy(way[c++],end);
        v=0;w=1;
        for(ca=0;ca<n;ca++){
            scanf("%s%s%d",temp1,temp2,&t);
            int w1,w2;
            w1=w2=0;
            for(i=0;i<c;i++){
                if(strcmp(temp1,way[i])==0)    {j=i;w1=1;}
                if(strcmp(temp2,way[i])==0)    {k=i;w2=1;}
                if(w1&&w2)    break;
            }
            if(w1==0){
                strcpy(way[c++],temp1);
                j=c-1;
            }
            if(w2==0){
                strcpy(way[c++],temp2);
                k=c-1;
            }
            if(length[j][k]==0||(length[j][k]!=0&&length[j][k]>t))
                length[j][k]=t;
            if(length[k][j]==0||(length[k][j]!=0&&length[k][j]>t))
                length[k][j]=t;
        }
        for(i=0;i<c;i++)
            for(j=0;j<c;j++)
                if(length[i][j]==0)
                    length[i][j]=maxint;
        for(i=0;i<c;i++){
            dist[i]=length[v][i];
            s[i]=false;
        }
        dist[v]=0;s[v]=true;
        for(i=0;i<c-1;i++){
            int temp=maxint;
            int u=v;
            for(j=0;j<c;j++)
                if((!s[j])&&(dist[j]<temp)){
                    u=j;
                    temp=dist[j];
                }
            s[u]=true;
            for(j=0;j<c;j++)
                if((!s[j])&&length[u][j]<maxint){
                    int newdist=dist[u]+length[u][j];
                    if (newdist<dist[j])
                        dist[j]=newdist;
                }
        }
        if(strcmp(start,end)==0)
            printf("0\n");
        else{
            if(dist[w]!=maxint)
                printf("%d\n",dist[w]);
            else
                printf("-1\n");
        }
    }
    return 0;
}