Tyvj 1176 火焰巨魔的惆悵

背景

TYVJ2月月賽第一道

巨魔家族在某天受到了其他種族的屠殺，作為一個(gè)英雄，他主動(dòng)擔(dān)任了斷后的任務(wù)，但是，在巨魔家族整體轉(zhuǎn)移過后，火焰巨魔卻被困住了，他出逃的方式也只有召喚小火人這一種方式，所以請你幫助他。

描述

我們把火焰巨魔所處的位置抽象成一張有向圖，他的位置就是1號點(diǎn)位，目的就是走到第N號點(diǎn)位，因?yàn)樾』鹑藭?huì)裂嘛，所以我們可以看做每走一條路，小火人的數(shù)量都會(huì)加倍，而每條路上的敵人有多強(qiáng)，會(huì)消耗多少小火人c[i]也會(huì)給出(c[i]為負(fù)值)；當(dāng)然有些時(shí)候路上也會(huì)遇到魔法泉之類的東西，這時(shí)候就可以補(bǔ)充一些小火人咯(c[i]為正值）。如果小火人死光了，那么火焰巨魔也就可以看做是掛了，畢竟智力型英雄就是脆啊。希望你幫助火焰巨魔用最少的初始小火人逃離這次屠殺。

輸入格式

第一行兩個(gè)數(shù)N（<=50000），M（<=100000）表示點(diǎn)位數(shù)與邊數(shù)。
一下M行，每行三個(gè)數(shù)a，b，c表示a，b兩點(diǎn)間的邊權(quán)是c（|c|<=10000）

輸出格式

輸出僅一個(gè)整數(shù)，表示最小初始小火人數(shù)。

測試樣例1

輸入

5 4?
1 2 -3?
1 3 -6?
3 4 1?
4 5 -9

輸出

4

備注

初始小火人為4個(gè)，到3點(diǎn)剩2個(gè)，到4變成5個(gè)，到5剩1個(gè)。
所以初始最少為4，更少的小火人是不足以走到5號點(diǎn)位的。from?wsd??TYVJ月賽出題組 思路： 1、由于要求的是從起點(diǎn)到達(dá)終點(diǎn)最少出發(fā)的小火人，所以是一個(gè)路徑尋找問題，所以要用到最短路 2、由于小火人最少是1，所以到終點(diǎn)后小火人數(shù)量一定是1，否則就必須要在起點(diǎn)派出更多小火人 3、在最短路中，目的是求長度最小，放入隊(duì)列的必要條件是可以把該點(diǎn)長度變小，所以此題中放入的條件是可以把所需要的火人數(shù)量變小 4、從終點(diǎn)開始，做spfa，則由用來松弛的點(diǎn)走到當(dāng)前節(jié)點(diǎn)的最小火人數(shù)設(shè)為x，則2x + g[now][i] = d[now]，可知x可能不為正整數(shù)，若為浮點(diǎn)數(shù)則向上取整，若x≤0，則將x設(shè)為1，然后去比較d[i]進(jìn)行松弛，最后d[1]便是正確答案 #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; const int maxn = 100005; const int maxint = ~0U>>1; struct edge{int v;int w; }; int n,m,vis[maxn],d[maxn]; vector<edge> g[maxn]; void input(){cin>>n>>m;int u,v,w;edge tmp;for(int i = 1;i <= m;i++){scanf("%d%d%d",&u,&v,&w);tmp.v = u;tmp.w = w;g[v].push_back(tmp);}for(int i = 1;i <= n;i++){vis[i] = 0;d[i] = maxint;} } void spfa(){queue<int> q;q.push(n);d[n] = 1;vis[n] = 1;int now,to,add;while(!q.empty()){now = q.front();q.pop();vis[now] = 0;for(int i = 0;i < g[now].size();i++){to = g[now][i].v;add = (d[now] - g[now][i].w) >> 1;if((d[now]-g[now][i].w) & 1) add++;if(add <= 0) add = 1;if(d[to] > add){d[to] = add;if(!vis[to]){vis[to] = 1;q.push(to);}}}} }int main(){input();spfa();cout<<d[1];return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/hyfer/p/5811828.html

總結(jié)

以上是生活随笔為你收集整理的Tyvj 1176 火焰巨魔的惆怅的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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