题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2019
题意：
奶牛们没钱了，正在找工作。农夫约翰知道后，希望奶牛们四处转转，碰碰运气。
而且他还加了一条要求：一头牛在一个城市最多只能赚D(1 <= D <= 1,000)美元，然后它必须到另一座城市工作。当然，它可以在别处工作一阵后又回来原来的城市再最多赚D美元。而且这样往往返返的次数没有限制。
城市间有P (1 <= P <= 150)条单向路径连接，共有N(2 <= N <= 220)座城市，编号1..N. 贝希当前处在城市S (1 <= S <= N)。路径 i 从城市A[i]到城市B[i](1 <= A[i] <= N, 1 <= B[i] <= N)，在路径上行走不用花任何费用。
为了帮助贝希，约翰让它使用他的私人飞机服务。这项服务有F条(1 <= F <= 350)航线，每条航线是从城市J[i]飞到另一座城市K[i](1 <=J[i] <= N, 1 <= K[i] <= N)，费用是T[i] (1 <= T[i] <= 50,000)美元。
如果贝希手中如果没有现钱，可以用以后赚的钱来付机票钱。
贝希可以选择任何时候，在任何城市退休。
如果在工作时间上不作限制，贝希总共可以赚多少钱呢？如果赚的钱也不会出现限制，就输出-1。
题解：
spfa找最长路。
如果有点入队超过n次，则存在正环，return -1。
建边：
（1）对于城市间的道路，边权设为D。
（2）对于航线，边权设为D - T[i]。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define MAX_N 250 using namespace std; struct Edge
{
int dest;
int len;
Edge(int _dest,int _len)
{
dest=_dest;
len=_len;
}
Edge(){}
}; int n,p,f,d,s;
int ans;
int dis[MAX_N];
int cnt[MAX_N];
bool vis[MAX_N];
vector<Edge> edge[MAX_N];
queue<int> q; void read()
{
cin>>d>>p>>n>>f>>s;
int a,b,c;
for(int i=;i<p;i++)
{
cin>>a>>b;
edge[a].push_back(Edge(b,d));
}
for(int i=;i<f;i++)
{
cin>>a>>b>>c;
edge[a].push_back(Edge(b,d-c));
}
} int get_front()
{
int now=q.front();
q.pop();
vis[now]=false;
return now;
} void insert(int now)
{
if(vis[now]) return;
q.push(now);
vis[now]=false;
cnt[now]++;
} int spfa(int start)
{
memset(dis,0x80,sizeof(dis));
memset(cnt,,sizeof(cnt));
memset(vis,false,sizeof(vis));
insert(start);
dis[start]=d;
int res=d;
while(!q.empty())
{
int now=get_front();
for(int i=;i<edge[now].size();i++)
{
Edge temp=edge[now][i];
if(dis[temp.dest]<dis[now]+temp.len)
{
dis[temp.dest]=dis[now]+temp.len;
insert(temp.dest);
if(cnt[temp.dest]>n) return -;
res=max(res,dis[temp.dest]);
}
}
}
return res;
} void solve()
{
ans=spfa(s);
} void print()
{
cout<<ans<<endl;
} int main()
{
read();
solve();
print();
}