hdu 1534 Schedule Problem

用最長路判斷。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
struct pi
{
    int no;
    int to;
    int cost;
    int next;
}pp[1000005];
int head[1000005],tot;
void add(int a,int b,int cost)
{
    pp[tot].no=a;
    pp[tot].to=b;
    pp[tot].cost=cost;
    pp[tot].next=head[a];
    head[a]=tot++;
    return ;
}
char c[5];
int dis[1000005];
int vis[1000005];
int a[1000005];
queue<int>q;
int main()
{
    int i,n,m,k,p,flag,N=0;
    long long ss;
    while(1)
    {
        cin>>n;
        if(!n)
            break;
        memset(head,-1,sizeof(head));
        tot=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&p);
            a[i]=p;
            add(0,i,0);
            dis[i]=-0x3f;
        }
        dis[0]=0;
        while(1)
        {
            scanf("%s",c);
            if(c[0]=='#')
            {
                break;
            }
            if(strcmp(c,"SAF")==0)
            {
                scanf("%d%d",&p,&m);
                add(m,p,a[m]);
            }
            else if(strcmp(c,"FAF")==0)
            {
                scanf("%d%d",&p,&m);
                add(m,p,a[m]-a[p]);
            }
            else if(strcmp(c,"FAS")==0)
            {
                scanf("%d%d",&p,&m);
                add(m,p,-a[p]);
            }
            else if(strcmp(c,"SAS")==0)
            {
                scanf("%d%d",&p,&m);
                add(m,p,0);
            }
        }
        memset(vis,0,sizeof(vis));
        vis[0]=1;
        while(!q.empty())
            q.pop();
        q.push(0);
        flag=0;ss=0;
        while(!q.empty())
        {
            k=q.front();
            q.pop();
            vis[k]=0;
            for(i=head[k];i!=-1;i=pp[i].next){
                if(dis[pp[i].to]<dis[k]+pp[i].cost)
                {
                    dis[pp[i].to]=dis[k]+pp[i].cost;
                    if(!vis[pp[i].to]){
                        vis[pp[i].to]=1;
                        q.push(pp[i].to);
                        ss++;
                    }
                }
            }
            if(ss>(long long)n*n)
            {
                flag=1;
                break;
            }
        }
        for(i=1;i<=n;i++){
            if(dis[i]<0)
            {
                flag=1;
                break;
            }
        }
        if(flag)
        {
            printf("Case %d:\n",++N);
            printf("impossible\n");
        }
        else{
             printf("Case %d:\n",++N);
            for(i=1;i<=n;i++)
            {
                printf("%d %d\n",i,dis[i]);
            }
        }
        printf("\n");
    }
    return 0;
}