题目描述
Bessie is running out of money and is searching for jobs. Farmer John knows this and wants the cows to travel around so he has imposed a rule that his cows can only make D (1 <= D <= 1,000) dollars in a city before they must work in another city. Bessie can, however, return to a city after working elsewhere for a while and again earn the D dollars maximum in that city. There is no limit on the number of times Bessie can do this.
Bessie's world comprises P (1 <= P <= 150) one-way paths connecting C (2 <= C <= 220) cities conveniently numbered 1..C. Bessie is currently in city S (1 <= S <= C). Path i runs one-way from city Ai to city Bi (1 <= Ai <= C; 1 <= Bi <= C) and costs nothing to traverse.
To help Bessie, Farmer John will give her access to his private jet service. This service features F (1 <= F <= 350) routes, each of which is a one way flight from one city Ji to a another Ki (1 <= Ji <= C; 1 <= Ki <= C) and which costs Ti (1 <= Ti <= 50,000) dollars. Bessie can pay for the tickets from future earnings if she doesn't have the cash on hand.
Bessie can opt to retire whenever and wherever she wants. Given an unlimited amount of time, what is the most money that Bessie can make presuming she can make the full D dollars in each city she can travel to? Print -1 if there is no limit to this amount.输入描述:
* Line 1: Five space-separated integers: D, P, C, F, and S * Lines 2..P+1: Line i+1 contains two space-separated integers that name a one-way path from one city to another: Ai and Bi * Lines P+2..P+F+1: Line P+i+1 contains three space-separated integers that name a one-way jet flight from one city to another and the price for that flight: Ji, Ki, and Ti输出描述:
* Line 1: A single integer representing the most money she can make while following the law.示例1
输入
复制
100 3 5 2 1 1 5 2 3 1 4 5 2 150 2 5 120输出
复制
250说明
This world has five cities, three paths and two jet routes. Bessie starts out in city 1, and she can only make 100 dollars in each city before moving on. Bessie can travel from city 1 to city 5 to city 2 to city 3, and make a total of 4*100 - 150 = 250 dollars.
AC代码:
- #include
- #include
- #include
- #include
- using namespace std;
-
- const int N=230,M=100010;
-
- int h[N],ne[M],e[M],w[M],idx;
- int d,m,n,f,s;
- int dist[N];
- bool st[N];
-
- void add(int a,int b,int c)
- {
- e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
- }
-
- void spfa()
- {
- memset(dist,-0x3f,sizeof dist);
- queue<int> q;
- dist[s]=d;
- q.push(s);
-
- while(q.size())
- {
- int t=q.front();
- q.pop();
- st[t]=0;
-
- for(int i=h[t];~i;i=ne[i])
- {
- int j=e[i];
- if(dist[j]
- {
- dist[j]=dist[t]+w[i];
- if(!st[j])
- {
- q.push(j);
- st[j]=1;
- }
- }
- }
- }
- }
-
- int main()
- {
- memset(h,-1,sizeof h);
- scanf("%d%d%d%d%d",&d,&m,&n,&f,&s);
- while(m--)
- {
- int a,b;
- cin>>a>>b;
- add(a,b,d);
- }
- while(f--)
- {
- int a,b,c;
- cin>>a>>b>>c;
- add(a,b,d-c);
- }
-
- spfa();
-
- int res=-0x3f3f3f3f;
- for(int i=1;i<=n;i++)
- res=max(res,dist[i]);
- cout<
- }
-
相关阅读:
Enzo丨Enzo 抗原回收试剂,pH 6方案
Java中的7种位运算详解和应用
wordpress遇到的问题
Vue项目引入translate.js 国际化自动翻译组件
CLion 使用 clang-cl 工具链时未正确链接 vcpkg 中的 Boost 外部库
社媒矩阵运营解决方案:海外云手机
Android Media Framework(三)OpenMAX API阅读与分析
springboot使用切面记录接口访问日志
国产3D自研技术如何突围?眸瑞科技给3D建设、管理带来全新模式
axure9设置组件自适应浏览器大小
-
原文地址:https://blog.csdn.net/qq_62242287/article/details/126671527