URAL 1741 Communication Fiend

連結：http://acm.timus.ru/problem.aspx?space=1&num=1741

題意：

kolya需要更新icq版本，從1版本更新到n版本，網上有些m個更新包，可以從版本sm更新到

em版本，這些更新包大小不一，

有些是正版Licensed，有些是盜版Pirated，有些是破解版Cracked，正版更新包隻能更新正版

軟體。

盜版更新包可以更新盜版軟體和正版軟體但是正版軟體會變成盜版。破解版可以更新盜版和正版

版本屬性不變。問最小下載下傳多大的更新包可以更新到版本n。

題解:

 dp,dp1[i]表示正版到版本i的空間大小，，，，

dp1[j]=min(dp1[j],dp1[i]+s(i,j),dp2[i]+s(i,j))

dp2[j]=min(dp2[j],dp1[i]+s(i,j),dp2[i]+s(i,j))

代碼：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#define INF 99999999999
#define LL long long
using namespace std;
struct data{
	int x,y,d,flag;
}a[10001];
LL dp1[10001],dp2[10001];
int cmp(data p,data q)
{
    return p.x<q.x;
}
int main()
{
	int n,m,i;
	string s;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].d);
		cin>>s;
		if(s=="Licensed")
			a[i].flag=0;
		else if(s=="Pirated")
			a[i].flag=1;
		else
			a[i].flag=2;
	}
	sort(a,a+m,cmp);
	for(i=0;i<=n;i++)        //這裡開始傻逼沒有初始化dp[n]調試了半晌%>_<%
		dp1[i]=dp2[i]=INF;
	dp1[1]=0;
	for(i=0;i<m;i++)
	{
		if(a[i].flag==0)
		{
			dp1[a[i].y]=min(dp1[a[i].x]+a[i].d,dp1[a[i].y]);
		}
		if(a[i].flag==1)
		{
			dp2[a[i].y]=min(dp1[a[i].x]+a[i].d,dp2[a[i].y]);
            dp2[a[i].y]=min(dp2[a[i].x]+a[i].d,dp2[a[i].y]);
		}
		if(a[i].flag==2)
		{
			dp1[a[i].y]=min(dp1[a[i].x]+a[i].d,dp1[a[i].y]);
			dp2[a[i].y]=min(dp2[a[i].x]+a[i].d,dp2[a[i].y]);
		}
	}
	LL ans=min(dp1[n],dp2[n]);
	if(ans>=INF)
	    printf("Offline\n");
	else
	{
		printf("Online\n");
		cout << ans << endl;
	}
	return 0;
}