來源：牛客網(wǎng)：

時(shí)間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 65536K，其他語言131072K 64bit IO Format: %lld

文章目錄

• • 題目描述
  • 題解：
  • 代碼：

題目描述

小明現(xiàn)在要追討一筆債務(wù)，已知有n座城市，每個(gè)城市都有編號(hào)，城市與城市之間存在道路相連（每條道路都是雙向的），經(jīng)過任意一條道路需要支付費(fèi)用。小明一開始位于編號(hào)為1的城市，欠債人位于編號(hào)為n的城市。小明每次從一個(gè)城市到達(dá)另一個(gè)城市需要耗時(shí)1天，而欠債人每天都會(huì)揮霍一定的錢，等到第k天后（即第k+1天）他就會(huì)離開城n并再也找不到了。小明必須要在他離開前抓到他（最開始為第0天），同時(shí)希望自己的行程花費(fèi)和欠債人揮霍的錢的總和最小，你能幫他計(jì)算一下最小總和嗎？

輸入描述:
第1行輸入三個(gè)整數(shù)n，m，k，代表城市數(shù)量，道路數(shù)量和指定天數(shù)
第2-m+1行，每行輸入三個(gè)整數(shù)u，v，w，代表起點(diǎn)城市，終點(diǎn)城市和支付費(fèi)用。（數(shù)據(jù)保證無重邊，自環(huán)）
第m+2行輸入k個(gè)整數(shù)，第i個(gè)整數(shù)ai代表第i天欠債人會(huì)揮霍的錢。
數(shù)據(jù)保證：0<n≤1000，0<m≤10000，0<k≤10，1≤u,v≤n，0<w,ai≤1000
輸出描述:
輸出一行，一個(gè)整數(shù)，代表小明的行程花費(fèi)和欠債人揮霍的錢的最小總和，如果小明不能抓住欠債人（即不能在第k天及之前到達(dá)城n），則輸出-1。
示例1
輸入
復(fù)制

3 3 2 1 3 10 1 2 2 2 3 2 3 7

輸出
復(fù)制

13

說明
小明從1-3,總共費(fèi)用=10（行程）+3（揮霍費(fèi)用）=13，是方案中最小的（另一條方案花費(fèi)14）。
示例2
輸入
復(fù)制

3 2 1 1 2 3 2 3 3 10

輸出
復(fù)制

-1

說明
小明無法在第1天趕到城3，所以輸出-1。

題解：

最短路問題
就是求最短路，并根據(jù)是第幾天加上相應(yīng)的數(shù)
松弛條件改為dis[d+1][v]>dis[d][u]+w+a[d+1]
dis[x][y]：x表示第x天，y為點(diǎn)
a[]：a存儲(chǔ)的第x天的揮霍費(fèi)用
記得特判能否在d天內(nèi)抓住嫌疑犯

代碼：

#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define SZ(x) (int)x.size() typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int mod=1e9+7; //const int mod=998244353; const double eps = 1e-10; const double pi=acos(-1.0); const int maxn=1e6+10; const ll inf=0x3f3f3f3f;struct node{int d,u,w;bool operator< (const node &p)const{return w>p.w;} }; int n,m,k; vector<pii> g[maxn]; int dis[1010][1010],a[maxn]; void dij(){memset(dis,inf,sizeof dis);dis[0][1]=0;priority_queue<node>q;q.push((node){0,1,0});while(!q.empty()){node p=q.top();q.pop();int u=p.u,d=p.d;if(p.w>dis[d][u])continue;for(auto i:g[u]){int v=i.fi,w=i.se;if(d+1<=k&&dis[d+1][v]>dis[d][u]+w+a[d+1]){dis[d+1][v]=dis[d][u]+w+a[d+1];q.push((node){d+1,v,dis[d+1][v]});}}} } int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);cin>>n>>m>>k;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;g[u].pb(mp(v,w));g[v].pb(mp(u,w));}for(int i=1;i<=k;i++)cin>>a[i];dij();int ans=inf;for(int i=1;i<=k;i++)ans=min(ans,dis[i][n]);if(ans!=inf)cout<<ans;else cout<<-1;return 0; }

總結(jié)

以上是生活随笔為你收集整理的【每日一题】8月6日题目精讲—追债之旅的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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