本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
题目背景
题目描述
zzy现在决定环游中国，顺便赚点钱。zzy在一个城市最多只能赚D元，然后他可以选择退休也就是停止赚钱，或者去其它城市工作。当然，他可以在别处工作一阵子后又回到原来的城市再赚D元。这样的往返次数是没有任何限制的。
城市间有P条单向路径连接，共有C座城市，编号从1到C。路径i从城市Ai到城市Bi，在路径行走上不用任何花费。
zzy还可以乘飞机从某个城市飞到另一个城市。共有F条单向的航线，第i条航线是从城市Ji飞到另一座城市Ki，费用是Ti元。假如zzy身上没有现钱，他可以用以后赚的钱来付机票钱。
zzy可以从任何一个城市出发开始赚钱，并且选择在任何时候、任何城市退休。现在zzy想要知道，如果在工作时间上不做限制，那么zzy共可以赚多少钱呢？如果赚的钱也不会出现限制，那么就输出orz。
输入格式
第一行，4个用空格分开的正整数，D，P，C，F。
第二行到P+1行，第i+1行包含2个用空格分开的整数，表示一条从城市Ai到城市Bi的单向路径。
接下来的F行，每行3个用空格分开的正整数，表示一条从城市Ji到城市Ki的单向航线，费用为Ti。
输出格式
如果zzy赚的钱没有限制，输出orz。如果有限制，那么就输出在给定的规则下zzy最多可以赚到的钱数。
输入输出样例
输入 #1
100 3 5 2
1 5
2 3
1 4
5 2 150
2 5 120
输出 #1
说明/提示
对于100%的数据，1<=D<=1000，1<=P<=200，2<=C<=300，1<=F<=400。
分析
这没啥好分析的，这就和我之前的题解一毛一样，只不过要一个一个枚举，xiu
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3;
int d,p,c,f;
int x,y,w;
int head[N],cnt;
bool ed[N][N];
int tot[N];
int dis[N];
bool vis[N],ju;
struct edge{
int to;
int ne;
int w;
}e[N];
void add(int u,int v,int w){
e[++cnt].to = v;
e[cnt].ne = head[u];
e[cnt].w = w;
head[u] = cnt;
}
void spfa(int s){
ju = 0;
for(int i = 1;i <= c;i++)dis[i] = -1e9;
memset(vis,0,sizeof(vis));
memset(tot,0,sizeof(tot));
queue<int>q;
q.push(s);
dis[s] = d;
vis[s] = 1;
while(!q.empty()){
int f = q.front();
q.pop();
vis[f] = 0;
for(int i = head[f];i;i = e[i].ne){
int v = e[i].to;
if(dis[v] < dis[f] + e[i].w){
tot[v]++;
if(tot[v]>c){
ju = 1;
return ;
}
dis[v] = dis[f] + e[i].w;
if(!vis[v]){
q.push(v);
vis[v] = 0;
}
}
}
}
}
int main(){
scanf("%d%d%d%d",&d,&p,&c,&f);
for(int i = 1;i <= p;i++){
scanf("%d%d",&x,&y);
ed[x][y] = 1;
add(x,y,d);
}
for(int i = 1;i <= f;i++){
scanf("%d%d%d",&x,&y,&w);
if(!ed[x][y]){
add(x,y,d-w);
}
}
int ans = -1e9;
for(int i = 1;i <= c;i++){
spfa(i);
if(ju == 1){
printf("orz\n");
return 0;
}
for(int j = 1;j <= c;j++){
ans = max(ans,dis[j]);
}
}
printf("%d\n",ans);
return 0;
}
