我们城市有几个货币兑换点在运作。让我们假设每个点专门针对两种特定货币
，并且仅使用这些货币执行交换操作。同一对货币可以有多个点。
每个点都有自己的汇率，A对B的汇率是1A的B数量。此外，每个兑换点都有一定的佣金
，即您必须为兑换业务支付的金额。佣金总是以来源货币收取。
例如，如果你想在汇率为29.75，佣金为0.39的兑换点将100美元兑换成俄罗斯卢布
，你将得到（100-0.39）*29.75=2963.3975卢布。你肯定知道在我们城市有N种不同的货币可以交易
。让我们为每种货币分配从1到N的唯一整数。然后，每个兑换点可以用6个数字来描述
：整数A和B——它兑换的货币数量，以及实际RAB、CAB、RBA和CBA——A兑换B和B兑换A时的汇率和佣金。
尼克有一些S币的钱，他想知道在一些兑换业务之后，他是否能以某种方式增加他的资本
。当然，他最终还是想把钱换成S货币。帮助他回答这个难题。尼克在做手术的时候必须有一笔非负的钱。
Input
输入的第一行包含四个数字：N-货币数量，M-兑换点数量，S-尼克拥有的货币数量，V-他拥有的货币单位数量
。以下M行各包含6个数字-对应交换点的描述-按上述顺序指定。
数字由一个或多个空格分隔。1<=S<=N<=100，1<=M<=100，V是实数，0<=V<=10^3。
对于每一点，汇率和佣金都是实数，小数点后最多有两位数字，10^-2<=rate<=10^2，0<=commission<=10^2
。如果在这个序列中没有一个兑换点被多次使用，那么让我们将一些兑换操作的序列称为简单的。
您可以假设任何简单的交换操作序列的末尾和开头的和的数值比率将小于10^4。（注：多组输入）
Output
如果Nick可以增加他的财富，则输出YES，在其他情况下，将NO输出到输出文件。
Sample Input
3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00
Sample Output
YES

#include<iostream>
#include<cstring>
#include<algorithm> 
#include<vector>
#include<queue>
using namespace std;

const int N=110;
int n,m,s;
double v;
bool st[N];
double dist[N];
struct node{
  int to; // 我想要兑换的货币类
    double p; // 汇率；
    double q; // 佣金
};
vector<node>V[N];
bool spfa()
{
    memset(st,false,sizeof st);
    memset(dist,0,sizeof dist);
    queue<int>q;
    q.push(s);
    dist[s]=v;
    st[s]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=0;i<V[t].size();i++)
        {
            int To=V[t][i].to;
            double P=V[t][i].p,Q=V[t][i].q;
            if(dist[To]<(dist[t]-Q)*P)
            {
                dist[To]=(dist[t]-Q)*P;
                if(dist[s]>v)return true;
                if(!st[To])
                {
                    q.push(To);
                    st[To]=true;
                }
            }
        }
    }
    return false;
}
int main()
{
    while(~scanf("%d%d%d%lf",&n,&m,&s,&v))
    {

        for(int i=1;i<=n;i++)
        {
            V[i].clear();
        }
        while(m--)
        {
            int a,b;
            double c,d;
            node e;
            scanf("%d%d%",&a,&b);
            scanf("%lf%lf",&c,&d);

            e.to=b,e.p=c,e.q=d;
            V[a].push_back(e);
            scanf("%lf%lf",&c,&d);

            e.to=a,e.p=c,e.q=d;
            V[b].push_back(e);

        }
        if(spfa())
        {
            printf("YES\n");
        }
        else
        {
                printf("NO\n");
        }
    }
    return 0;
} 

耳机楼里有很多教室，这些教室由双向走廊连接。另外，还存在一些单向的秘密通道
，通过它们可以回到过去。现在有 N (1 ≤ N ≤ 500) 个教室，
编号 1..N, M (1 ≤ M ≤ 2500) 条走廊，和 W (1 ≤ W ≤ 200) 条秘密通道。
DY在养猫之余，还是一个时间旅行爱好者。她希望从一间教室出发，经过一些走廊和秘密通道
，回到她出发之前的某个时间。
共有F (1 ≤ F ≤ 5) 组数据。对每组数据，判断DY是否有回到过去的可能性。
不存在耗时超过10,000秒的走廊，且不存在能带DY回到10,000秒之前的秘密通道。
Input
首先是一个整数F，表示接下来会有F组数据。
每组数据第1行：分别是三个空格隔开的整数：N，M和W
第2行到M+1行：三个空格分开的数字（S，E，T）描述双向走廊：从S到E需要耗费T秒。
两个教室可能由一个以上的路径来连接。
第M +2到M+ W+1行：三个空格分开的数字（S，E，T）描述秘密通道：从S到E可以使时间倒流T秒
Output
F行，每行对应一组数据。 每组数据输出单独的一行，” YES”表示能满足要求，”NO”表示不能满足要求。
Sample Input
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
Sample Output
NO
YES

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue> 
using namespace std;

const int N=5210;
int dist[N],cnt[N];
bool st[N];
int h[N],e[N],w[N],ne[N],idx;
int n,m,W;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool spfa()
{
    memset(dist,0,sizeof dist);
    memset(cnt,0,sizeof cnt);
    memset(st,false,sizeof st);
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        q.push(i);
        st[i]=true;
    }
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n)return true;
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(h,-1,sizeof h);
        idx=0;
        scanf("%d%d%d",&n,&m,&W);
        int a,b,c;
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        while(W--)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,-c);
        }
        if(spfa())
        {
            puts("YES");

        }
        else
        {
            puts("NO");
        }
    }
    return 0;
} 

年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。
酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币
，便请求酋长降低要求。酋长说："嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。
如果你能够弄来他的水晶球，那么只要5000金币就行了。"探险家就跑到大祭司那里
，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格
。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，
或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格
。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，
在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，
包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易
，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。
因此你需要在考虑所有的情况以后给他提供一个最好的方案。
为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，
并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，
以及一系列的替代品Ti和该替代品所对应的"优惠"Vi。如果两人地位等级差距超过了M，
就不能"间接交易"。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。
Input
输入第一行是两个整数M，N（1 <= N <=
100），依次表示地位等级差距限制和物品的总数。
接下来按照编号从小到大依次给出了N个物品的描述。
每个物品的描述开头是三个非负整数P、L、X（X <
N），依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V，
分别表示替代品的编号和"优惠价格"。
Output
输出最少需要的金币数。
Sample Input
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0
Sample Output
5250

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

#define INF 0x3f3f3f3f

int n, m;
int g[N][N];
int level[N];
bool st[N];
int dist[N];

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);

    for (int i = 1; i <= n; i ++ )

        dist[i] = g[0][i];

    for (int i = 1; i <= n; i ++ ) {

        int t = -1;

        for (int j = 1; j <= n; j ++ )

            if (!st[j] && (t == - 1 || dist[j] < dist[t]))
                t = j;
        st[t] = true;

        for (int j = 1; j <= n; j ++ )

            if (!st[j] && g[t][j])
                dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    return dist[1];
}

int main() {
    scanf("%d%d", &m, &n);

    for (int i = 1; i <= n; i ++ ) {

        int q;
        scanf("%d%d%d", &g[0][i], &level[i], &q);

        while (q -- ) {
            int ver, price;
            scanf("%d%d", &ver, &price);
            g[ver][i] = price;
        }
    }

    int MAX; // 酋长的等级不一定是最高的
    int min_price = INF;

    for (int i = 1; i <= n; i ++ ) {

        MAX = level[i];

        for (int j = 1; j <= n; j ++ ) {

            if (level[j] > MAX || MAX - level[j] > m)
                st[j] = true;
            else
                st[j] = false;
        }

        int ans = dijkstra();

        if (min_price > ans)
            min_price = ans;
    }

    printf("%d\n", min_price);
    return 0;
}

弗莱迪青蛙正坐在湖中央的一块石头上。突然，他注意到Fiona Frog坐在另一块石头上。他计划去看她，但由于水很脏，而且充满了游客的防晒霜，
他想避免游泳，而是通过跳跃来接触她。 不幸的是菲奥娜的石头超出了他的跳跃范围。因此，弗雷迪考虑用其他石头作为中间站，
通过几个小跳跃的顺序到达她。 要执行一个给定的跳跃序列，青蛙的跳跃范围显然必须至少与该序列中最长的一次跳跃一样长。 因此，两块石头之间的蛙距离（人类也称之为极大极小距离）
被定义为两块石头之间所有可能路径上的最小必要跳跃范围。 你得到了弗雷迪之石、菲奥娜之石和湖里所有其他石头的坐标
。你的工作是计算Freddy和Fiona的石头之间的距离。
Input
输入将包含一个或多个测试用例。每个测试用例的第一行将包含石块数量n（2 <= n <=
200）。下一行n包含两个整数Xi，Yi（0 ＜＝ Xi，Yi <＝ 1000），表示石头席席I的坐标。石头#1是弗雷迪的石头#2是菲奥娜的石头#其他n-2的石头都没人用
。每个测试用例后面都有一个空行。对于n，输入端的值为零（0）。
Output
对于每个测试用例，打印一行“Scenario#x”和一行“Frog Distance=y”，其中x由测试用例编号替换（从1开始编号），y由适当的实数替换，
打印为三位小数。在每个测试用例之后，甚至在最后一个测试用例之后，都放一个空行。
Sample Input
2
0 0
3 4

3
17 4
19 4
18 5

0
Sample Output
Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 210;

#define INF 0x3f3f3f3f

int n;
double g[N][N];
int casei;
double dist[N];
bool st[N];

struct node {
    double x;
    double y;
} spot[N];

double dijkstra() {
    memset(st, false, sizeof st);

    for (int i = 1; i <= n; i ++ )

        dist[i] = INF;
    dist[1] = 0;

    for (int i = 1; i < n; i ++ ) {

        int t = -1;

        for (int j = 1; j <= n; j ++ )

            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        st[t] = true;

        for (int j = 1; j <= n; j ++ )

            dist[j] = min(dist[j], max(dist[t], g[t][j]));//最长路的最短边
    }

    return dist[2];
}

int main() {
    while (~scanf("%d", &n)) {
        if (n == 0)
            break;

        for (int i = 1; i <= n; i ++ )

            scanf("%lf%lf", &spot[i].x, &spot[i].y);

        for (int i = 1; i <= n; i ++ )

            for (int j = 1; j <= n; j ++ )

                if (i != j)
                    g[i][j] = sqrt(pow(spot[i].x - spot[j].x, 2) + pow(spot[i].y - spot[j].y, 2));
        double ans = dijkstra();
        printf("Scenario #%d\n", ++ casei);
        printf("Frog Distance = %.3lf\n\n", ans);
    }

    return 0;
}