学步园

链接：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;
}