CQUPT 最短路

题解

POJ 1125:STOCKBROKER GRAPEVINE
题意：
给出一幅有向图，计算出以哪个点为起点时，最大最短路距离最小。输出起点与距离。
思路：
迪杰斯特拉算法执行n次，需要注意的是判断某一点不可达时，是判断d[i]是否与inf相等。
代码：

#include <stdio.h>
#include <string.h>
int mmp[105][105];
int vis[105];
int d[105];
const int inf = 100000000;
int main()
{
    int n;
    while (scanf("%d",&n) == 1 && n)
    {
        memset(mmp,0,sizeof(mmp));
        memset(d,0,sizeof(d));
        memset(vis,0,sizeof(vis));
        for (int i = 0;i < 105;i++)
            for (int j = 0;j < 105;j++)
            mmp[i][j] = inf;
        for (int i = 0;i < 105;i++)
        {
            mmp[i][i] = 0;
            d[i] = inf;
        }
        for (int i = 1;i <= n;i++)
        {
            int c;
            scanf("%d",&c);
            for (int j = 1;j <= c;j++)
            {
                int to,dis;
                scanf("%d%d",&to,&dis);
                mmp[i][to] = dis;
            }
        }
        int dissum = 0,mark = 0;
        int minn = inf;
        for (int i = 1;i <= n;i++)
        {
            int sumdis = 0;
            memset(vis,0,sizeof(vis));
            for (int j = 1;j <= n;j++)
                d[j] = inf;
            d[i] = 0;
            for (int j = 1;j <= n;j++)
            {
                int x,m = inf;
                for (int y = 1;y <= n;y++)
                    if (!vis[y] && d[y] <= m) m = d[x=y];
                vis[x] = 1;
                for (int y = 1;y <= n;y++)
                    if (d[y] > d[x] + mmp[x][y])
                        d[y] = d[x] + mmp[x][y];
            }
            for (int j = 1;j <= n;j++)
                if (d[j] == inf)
                {
                    dissum++;
                    continue;
                }
            for (int j = 1;j <= n;j++)
                if (d[j] > sumdis)
                    sumdis = d[j];
            if (sumdis < minn)
            {
                mark = i;
                minn = sumdis;
            }
        }
        if (dissum == n) printf("disjoint\n");
        else printf("%d %d\n",mark,minn);
    }
    return 0;
}

poj 3259：WORMHOLES
题意：
给出一幅图，边权为正的边是双向的，边权为负的边是单向的，问是否存在负环。
思路：
bell-ford算法，这是一道（模版题。如果图中存在负环，则在算法执行过程中经过某一个点会超过1次。
代码：

#include <stdio.h>
#include <string.h>
typedef struct edge
{
    int s,e;
    int t;
}edge;
edge edg[5300];
int d[505];
int main()
{
    int f;
    scanf("%d",&f);
    for (int o = 1;o <= f;o++)
    {
        int n,m,w;
        memset(edg,0,sizeof(edg));
        scanf("%d%d%d",&n,&m,&w);
        int sume = 0;
        for (int i = 0;i < m;i++)
        {
            int sta,sto,l;
            scanf("%d%d%d",&sta,&sto,&l);
            edg[sume].s = sta;
            edg[sume].e = sto;
            edg[sume].t = l;
            sume++;
            edg[sume].s = sto;
            edg[sume].e = sta;
            edg[sume].t = l;
            sume++;
        }
        for (int i = 0;i < w;i++)
        {
            int sta,sto,l;
            scanf("%d%d%d",&sta,&sto,&l);
            edg[sume].s = sta;
            edg[sume].e = sto;
            edg[sume].t = -l;
            sume++;
        }
        //printf("%d %d\n",w+m*2,sume);
        memset(d,0,sizeof(d));
        int flag = 0;
        for (int i = 0;i < n;i++)
            for (int j = 0;j < sume;j++)
        {
            edge tmp = edg[j];
            if (d[tmp.e] > d[tmp.s] + tmp.t)
            {
                d[tmp.e] = d[tmp.s] + tmp.t;
                if (i == n-1)
                    flag = 1;
            }
        }
        if (flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

poj1026:昂贵的聘礼
题意：
中文题。
思路：
看了题解报告才写出来，菜！
原来卡住的地方是不知道如何使用这个等级，后来知道原来是在一个等级区间范围内的点可以进行最短路。
之后呢，就是如何表示等级区间啦，比如说，m为4，而酋长的等级为2的时候，等级区间就是1到5，2到6，就没有啦，因为必须包含酋长嘛，以此类推。之后就没有什么困难的啦，不过要改掉依赖模板的习惯。
坑：第一是自己把循环变量给用混了，神特么用混啊，思维不够严谨。第二呢是受题的样例的影响，觉得酋长的初始值一直都是10000，QAQ。
好的地方：一开始我觉得这题做不出来，好烦啊。但是后来静下心来思考之后，虽然借助了题解报告，但是还是把这道题给做出来了，看来做一切事情之前都要静下心来，才能做的好啊。
代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int g[105][105];
int d[105];
bool vis[105];
int lev[105];
int m,n;
const int inf = 100000000;
int dij(int l,int r)
{
    memset(vis,0,sizeof(vis));
    for (int i = 0;i <= n;i++) d[i] = (i == 0 ? 0 : inf);
    lev[0] = l;
    for (int i = 0;i < n;i++)
    {
        int x,tmp = inf;
        for (int j = 0;j <= n;j++)
        {
            if (lev[j] >= l && lev[j] <= r)
            {
                if (!vis[j] && d[j] <= tmp)
                   tmp = d[x = j];
            }
        }
        vis[x] = 1;
        for (int j = 0;j <= n;j++)
        {
            if (lev[j] >= l && lev[j] <= r)
            {
                d[j] = min(d[j],d[x] + g[x][j]);
            }
        }
    }
    return d[1];
}
int main()
{
    while (scanf("%d%d",&m,&n) != EOF)
    {
        for (int i = 0;i < 105;i++)
            for (int j = 0;j < 105;j++)
                g[i][j] = 100000000;
        for (int i = 0;i < 105;i++) g[i][i] = 0;
        for (int i = 1;i <= n;i++)
        {
            int p,x;
            scanf("%d%d%d",&p,&lev[i],&x);
            g[0][i] = p;
            for (int j = 1;j <= x;j++)
            {
                int t,v;
                scanf("%d%d",&t,&v);
                g[t][i] = v;
            }
        }
        //printf("%d\n",g[4][1]);
        int ans = g[0][1];
        int l,r;
        if (lev[1] - m <= 0)
        {
            l = 1;
            r = l+m;
        }
        else
        {
            l = lev[1] - m;
            r = lev[1];
        }
        for (int i = 0;l + i <= lev[1];i++)
        {
            int tmp;
            tmp = dij(l+i,r+i);
            if (tmp < ans)
                ans = tmp;
        }
        printf("%d\n",ans);
    }
    return 0;
}