rual 1741.Communication Fiend

http://acm.timus.ru/problem.aspx?space=1&num=1741
タイトルの大意:
主人公がクライアントをアップグレードしたいのですが、現在のバージョンは 1 Licensed
最速でバージョンnにアップグレードしたいです。
m個 ugrade programs
それぞれ属性xがあります。 y d s
バージョンxをバージョンyにアップグレードできるという意味です。 dはサイズが小さいほどダウンロードが早いです。 sタイプはLicensedがあります。    クラック   Piratedの3種類
レベルアップは制限があります。xからレベルアップします。現在のバージョンはxです。   
PiratedにアップグレードされたらどんなタイプでもPiratedです。
LicensedはPiratedバージョンでアップグレードできません。
必要なソフトウェアのdと最小
届かない場合があります。
ans 0[i]はバージョンiにアップグレードされ、タイプがPiratedの最小時間を表します。
ans 1[i]はバージョンiにアップグレードし、タイプがPiratedでない最小時間を表します。
m個のup grade programsをxで並べ替えてansを更新して最後に二つの状況の一番心配な答えを取って比較します。
コードとそのコメント:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<queue>

#include<stack>

#include<cmath>

#define LL long long



using namespace std;

const int N=10005;

const LL INF=0xffffffffffff;//  

LL ans0[N];//     i     Pirated     

LL ans1[N];//     i      Pirated      

struct node

{

    int x,y,d,k;

}program[N];//    

bool cmp(node a,node b)

{

    return a.x<b.x;

}

LL Fmin(LL a,LL b)

{

    if(a<b)

    return a;

    return b;

}

void dp(int m)

{

    ans1[1]=0;//   

    for(int i=0;i<m;++i)

    {

        int x=program[i].x;

        int y=program[i].y;

        int k=program[i].k;

        int d=program[i].d;

        if(ans0[x]<INF&&k!=2)//   k！=2    Licensed    Pirated   

        {

            ans0[y]=Fmin(ans0[y],ans0[x]+d);

        }

        if(ans1[x]<INF)

        {

            if(k==0)//      

            {ans0[y]=Fmin(ans0[y],ans1[x]+d);}

            else

            {ans1[y]=Fmin(ans1[y],ans1[x]+d);}

        }

    }

}

int main()

{

//   freopen("data","r",stdin);

    int n,m;

    while(scanf("%d %d",&n,&m)!=EOF)

    {

        char stemp[10];

        for(int i=1;i<=n;++i)

        ans0[i]=ans1[i]=INF;

        for(int i=0;i<m;++i)

        {

            scanf("%d %d %d %s",&program[i].x,&program[i].y,&program[i].d,stemp);

            if(stemp[0]=='L')//           

            program[i].k=2;

            else if(stemp[0]=='C')

            program[i].k=1;

            else

            program[i].k=0;

        }

        sort(program,program+m,cmp);// x  

        dp(m);

        LL ans=Fmin(ans0[n],ans1[n]);//   

        if(ans==INF)

        printf("Offline
");

        else

        {

            printf("Online
");

            cout<<ans<<endl;

        }

    }

    return 0;

}