hdu 3631 Shortest Path

水题~

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cassert>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=311;
const int maxc=100111;
const int inf=0x3f3f3f3f;
struct 
{
    int e;
    int x,y;    
}zout[maxc];    //1 wrong x //2 wrong x y //3 way x// 4 no way
struct zz
{
    int sta;
    int end;
    int id;
}zx,vz[maxc];   
int t1,t2;
int n,m,qq,tx,ty,tc,jet,vnow;
int way[maxn][maxn];
bool you[maxn];


void floyd()
{
    int temp;
    if(vnow == -1)
    {          
        return ;
    }
    for(int i=0;i<n;i++)
    { 
        if(way[i][vnow] == inf ) continue;                  
        for(int j=0;j<n;j++)
        {
            if(way[vnow][j] == inf) continue;
            temp = way[i][vnow] + way[vnow][j];
            if(temp < way[i][j])
            {
                way[i][j]=temp;
            }
        }
    }
    return ;
}

int main()
{
    int cas=1;
    while(scanf("%d%d%d",&n,&m,&qq)!=EOF)
    {   
        t1=1;
        t2=1;
        if(!n && !m && !qq) break;     
        if(cas!=1)
        {
            printf("\n");
        } 
        printf("Case %d:\n",cas++);
        for(int i=0;i<n;i++)      
        {
            for(int j=0;j<n;j++)
            {
                way[i][j] = inf;    
            }
            way[i][i] = 0;
        }
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&tx,&ty,&tc);
            if( tc < way[tx][ty] )
            {
                way[tx][ty] = tc;
            }        
        }
        memset(you,false,sizeof(you));
        vnow = -1;
        for(int i=1; i<=qq; i++)
        {
            scanf("%d",&jet);
            if(!jet)
            {
                scanf("%d",&tx);
                if(you[tx]) 
                {
                    zout[t1].e = 1;
                    zout[t1].x = tx;
                    t1++;
                }           
                else
                {
                    floyd();
                    if(t2!=1)
                    {
                        for(int j=1; j<t2; j++)
                        {
                            zout[vz[j].id].x = way [ vz[j].sta ][ vz[j].end ];
                            if(zout[vz[j].id].x == inf)
                            {
                                zout[vz[j].id].e=4;
                            }
                        }
                        t2 = 1;
                    }    
                    vnow=tx;
                    you[tx]=true;
                }
            }       
            else
            {
                scanf("%d%d",&tx,&ty);
                if(you[tx] && you[ty])
                {   
                    vz[t2].sta = tx;
                    vz[t2].end = ty;
                    vz[t2].id = t1;
                    t2++;  
                    zout[t1++].e = 3;
                }
                else
                {
                    zout[t1].x = tx;
                    zout[t1].y = ty;
                    zout[t1++].e = 2;
                }
            }
        }
        if(t2!=1)
        {
            floyd();
            for(int i=1;i<t2;i++)
            {
                zout[vz[i].id].x = way [ vz[i].sta ][ vz[i].end ];
                if(zout[vz[i].id].x == inf)
                {
                   zout[vz[i].id].e=4;
                }
            }
            t2=1;
        }
        for(int i=1;i<t1;i++)
        {
            if(zout[i].e==1)
            {
                printf("ERROR! At point %d\n",zout[i].x);
            }
            else if(zout[i].e==2)
            {
                printf("ERROR! At path %d to %d\n",zout[i].x,zout[i].y);
            }
            else if(zout[i].e==3)
            {   
                printf("%d\n",zout[i].x);    
            }
            else if(zout[i].e==4)
            {
                printf("No such path\n");
            }
            else
            {
                assert(false);
            }
        }
    }    
    return 0;
}