http://acm.timus.ru/problem.aspx?space=1&num=1741
題目大意：
主人翁需要升級客戶端 現在的版本是 ?1 ?Licensed
想以最快速度升級到版本 n
m 個? upgrade programs
每一個都有屬性 x ?y ?d ?s
表示可以將版本x 升級到版本 y ?d為它的大小 越小下載越快 ?s為類型 有 Licensed ? ? Cracked ? ? Pirated三種
升級是有限制的 從x開始升級必須 當前版本就是x ? ?
一旦被Pirated升級后 無論再用什么類型升級 都還是 Pirated
Licensed不可以在Pirated版本上升級
要求所以用到的軟件的d的和 最小
存在達不到的情況
ans0[i]表示升級到版本i 且類型為Pirated的最小時間
ans1[i]表示升級到版本i 且類型為非Pirated的最小時間
將m個upgrade 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\n");
else
{
printf("Online\n");
cout<<ans<<endl;
}
}
return 0;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
