网站商城网络整合营销,wordpress标签加标题,南京建设企业网站,影视公司招聘信息来源#xff1a;牛客网#xff1a;
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 65536K#xff0c;其他语言131072K
64bit IO Format: %lld文章目录题目描述题解#xff1a;代码#xff1a;题目描述 小明现在要追讨一笔债务#xff0c…来源牛客网
时间限制C/C 1秒其他语言2秒
空间限制C/C 65536K其他语言131072K
64bit IO Format: %lld文章目录题目描述题解代码题目描述 小明现在要追讨一笔债务已知有n座城市每个城市都有编号城市与城市之间存在道路相连每条道路都是双向的经过任意一条道路需要支付费用。小明一开始位于编号为1的城市欠债人位于编号为n的城市。小明每次从一个城市到达另一个城市需要耗时1天而欠债人每天都会挥霍一定的钱等到第k天后即第k1天他就会离开城n并再也找不到了。小明必须要在他离开前抓到他最开始为第0天同时希望自己的行程花费和欠债人挥霍的钱的总和最小你能帮他计算一下最小总和吗 输入描述: 第1行输入三个整数nmk代表城市数量道路数量和指定天数 第2-m1行每行输入三个整数uvw代表起点城市终点城市和支付费用。数据保证无重边自环 第m2行输入k个整数第i个整数ai代表第i天欠债人会挥霍的钱。 数据保证0n≤10000m≤100000k≤101≤u,v≤n0w,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。
题解
最短路问题 就是求最短路并根据是第几天加上相应的数 松弛条件改为dis[d1][v]dis[d][u]wa[d1] dis[x][y]x表示第x天y为点 a[]a存储的第x天的挥霍费用 记得特判能否在d天内抓住嫌疑犯
代码
#includebits/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 pairint, int pii;
typedef pairll, ll pll;
const int mod1e97;
//const int mod998244353;
const double eps 1e-10;
const double piacos(-1.0);
const int maxn1e610;
const ll inf0x3f3f3f3f;struct node{int d,u,w;bool operator (const node p)const{return wp.w;}
};
int n,m,k;
vectorpii g[maxn];
int dis[1010][1010],a[maxn];
void dij(){memset(dis,inf,sizeof dis);dis[0][1]0;priority_queuenodeq;q.push((node){0,1,0});while(!q.empty()){node pq.top();q.pop();int up.u,dp.d;if(p.wdis[d][u])continue;for(auto i:g[u]){int vi.fi,wi.se;if(d1kdis[d1][v]dis[d][u]wa[d1]){dis[d1][v]dis[d][u]wa[d1];q.push((node){d1,v,dis[d1][v]});}}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//freopen(in.txt,r,stdin);//freopen(out.txt,w,stdout);cinnmk;for(int i1;im;i){int u,v,w;cinuvw;g[u].pb(mp(v,w));g[v].pb(mp(u,w));}for(int i1;ik;i)cina[i];dij();int ansinf;for(int i1;ik;i)ansmin(ans,dis[i][n]);if(ans!inf)coutans;else cout-1;return 0;
}
