NC14700. 追债之旅
描述
小明现在要追讨一笔债务，已知有n座城市，每个城市都有编号，城市与城市之间存在道路相连（每条道路都是双向的），经过任意一条道路需要支付费用。小明一开始位于编号为1的城市，欠债人位于编号为n的城市。小明每次从一个城市到达另一个城市需要耗时1天，而欠债人每天都会挥霍一定的钱，等到第k天后（即第k+1天）他就会离开城n并再也找不到了。小明必须要在他离开前抓到他（最开始为第0天），同时希望自己的行程花费和欠债人挥霍的钱的总和最小，你能帮他计算一下最小总和吗？
输入描述
第1行输入三个整数n，m，k，代表城市数量，道路数量和指定天数第2-m+1行，每行输入三个整数u，v，w，代表起点城市，终点城市和支付费用。（数据保证无重边，自环）第m+2行输入k个整数，第i个整数ai代表第i天欠债人会挥霍的钱。数据保证：0<n≤1000，0<m≤10000，0<k≤10，1≤u,v≤n，0<w,ai≤1000
输出描述
输出一行，一个整数，代表小明的行程花费和欠债人挥霍的钱的最小总和，如果小明不能抓住欠债人（即不能在第k天及之前到达城n），则输出-1。
示例1
输入:
3 3 2 1 3 10 1 2 2 2 3 2 3 7
输出:
13
说明:
小明从1-3,总共费用=10（行程）+3（挥霍费用）=13，是方案中最小的（另一条方案花费14）。示例2
输入:
3 2 1 1 2 3 2 3 3 10
输出:
-1
说明:
小明无法在第1天赶到城3，所以输出-1。pypy3(pypy3.6.1) 解法, 执行用时: 459ms, 内存消耗: 36080K, 提交时间: 2020-08-27 17:56:20
#!/usr/bin/env python3 # # 追债之旅 # import sys, os, math, re, time, random, copy, shutil, itertools, functools, heapq def read_ints(): return list(map(int, input().split())) n, m, k = read_ints() g = [[] for _ in range(n)] for _ in range(m): u, v, w = read_ints() g[u - 1].append([v - 1, w]) g[v - 1].append([u - 1, w]) c = read_ints() def sp(g, src, c): dist = [[1e18] * (k + 1) for _ in range(len(g))] dist[src][0] = 0 q = [(0, 0, src)] while q: _, i, u = heapq.heappop(q) for v, w in g[u]: cost = dist[u][i] + w + c[i] if cost < dist[v][i + 1]: dist[v][i + 1] = cost if i + 1 < k: heapq.heappush(q, (cost, i + 1, v)) return dist d = sp(g, 0, c) ans = min(d[-1]) print(ans if ans < 1e18 else -1)
C++11(clang++ 3.9) 解法, 执行用时: 47ms, 内存消耗: 8072K, 提交时间: 2020-08-09 21:12:14
#include<bits/stdc++.h>
using namespace std;
int d[10005][10005],n,m,k;
int ans=0x3f3f3f3f,q[10005],mark[10005];
void dfs(int x,int t,int s)
{
if(s>ans)
return;
if(x==n)
{
ans=min(ans,s);
return;
}
for(int i=1;i<=n;i++)
{
if(d[x][i]!=0&&mark[i]==0&&t<=k)
{
mark[i]=1;
dfs(i,t+1,s+d[x][i]+q[t]);
mark[i]=0;
}
}
}
int main()
{
int x,y,z;
cin>>n>>m>>k;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
d[x][y]=d[y][x]=z;
}
for(int i=1;i<=k;i++)
scanf("%d",&q[i]);
dfs(1,1,0);
if(ans!=0x3f3f3f3f)
cout<<ans;
else
cout<<"-1";
return 0;
}
C++14(g++5.4) 解法, 执行用时: 28ms, 内存消耗: 4392K, 提交时间: 2020-08-10 16:56:05
#include<bits/stdc++.h>
using namespace std;
int d[1005][1005],n,m,k;
int ans=0x3f3f3f3f,q[11],mark[1005];
void dfs(int x,int t,int s)
{
if(s>ans)
return;
if(x==n)
{
ans=min(ans,s);
return;
}
for(int i=2;i<=n;i++)
{
if(d[x][i]!=0&&mark[i]==0&&t<=k)
{
mark[i]=1;
dfs(i,t+1,s+d[x][i]+q[t]);
mark[i]=0;
}
}
}
int main()
{
int x,y,z;
cin>>n>>m>>k;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
d[x][y]=d[y][x]=z;
}
for(int i=1;i<=k;i++)
scanf("%d",&q[i]);
dfs(1,1,0);
if(ans!=0x3f3f3f3f)
cout<<ans;
else
cout<<"-1";
return 0;
}