P1476 休息中的小呆

題目描述

當大家在考場中接受考驗（折磨？）的時候，小呆正在悠閑（欠扁）地玩一個叫“最初夢想”的游戲。游戲描述的是一個叫pass的有志少年在不同的時空穿越對抗傳說中的大魔王chinesesonic的故事。小呆發(fā)現(xiàn)這個游戲的故事流程設計得很復雜，它有著很多的分支劇情，但不同的分支劇情是可以同時進行的，因此游戲可以由劇情和劇情的結束點組成，某些劇情必須要在一些特定的劇情結束后才能繼續(xù)發(fā)展。為了體驗游戲的完整性，小呆決定要看到所有的分支劇情——完成所有的任務。但這樣做會不會耽誤小呆寶貴的睡覺時間呢？所以就請你來解決這個問題了。

輸入輸出格式

輸入格式：

?

小呆會給你一個劇情流程和完成條件的列表，

其中第一行有一個數(shù)n（0<n<100），表示總共有n個劇情結束點，

第二行一個數(shù)m(0<m<=120)，表示有m個不同的劇情，

下面的m行中每行有三個數(shù)i(0<i<=100),j(0<j<=100),k(0<k<=1000)，表示從劇情結束點i必須完成一個耗費時間為k的劇情才能到達劇情結束點j。

?

輸出格式：

?

你要告訴小呆完成整個游戲至少需要多少時間以及要經(jīng)過的所有可能的劇情結束點（按升序輸出）。

?

輸入輸出樣例

輸入樣例#1：
4 5 1 2 2 2 3 2 3 5 3 1 4 3 4 5 3 輸出樣例#1：
7 1 2 3 5

這里是求最長路并且結點個數(shù)+1

1、存儲圖：看數(shù)據(jù)量，這里是100，鄰接矩陣

2、floyed優(yōu)化：I,j,k不等并且用來dp的值有值

3、輸出優(yōu)化點：更新過別人的點

?

1 #include <bits/stdc++.h> 2 const int N=1e2+10; 3 using namespace std; 4 int dp[N][N],n,m; 5 6 int main(){ 7 //freopen("in.txt","r",stdin); 8 cin>>n>>m; 9 for(int i=1;i<=m;i++){ 10 int u,v,w; 11 cin>>u>>v>>w; 12 dp[u][v]=w; 13 } 14 for(int k=1;k<=n+1;k++){ 15 for(int i=1;i<=n+1;i++){ 16 for(int j=1;j<=n+1;j++){ 17 if(i!=j&&j!=k&&dp[i][k]&&dp[k][j]){ 18 dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]); 19 } 20 } 21 } 22 } 23 cout<<dp[1][n+1]<<endl; 24 for(int k=1;k<=n+1;k++){ 25 if(dp[1][n+1]==dp[1][k]+dp[k][n+1]) 26 cout<<k<<" "; 27 } 28 cout<<endl; 29 return 0; 30 }

?

?

總結

以上是生活随笔為你收集整理的P1476 休息中的小呆的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。