洛谷——P2559 [AHOI2002]哈利·波特与魔法石

墨蓝 2021-09-20 07:12 271阅读 0赞

# P2559 \[AHOI2002\]哈利·波特与魔法石 #

## 题目描述 ##

![1681.png][]

## 输入输出格式 ##

**输入格式：**

文件中第一行有七个数，分别是 S1、 S2 、 …、 S7 ；第二行有两个数，依次分别是起点城市 i 和终点城市 j ；第三行有一个正整数 c ，c<=10000， 表示随后的 c 行中每行存放了一对能直接通达的城市的信息。 能直接通达的城市的信息由三个数组成， 依次分别是两个城市的编号和这两个城市之间的地形。城市的编号都是不超过 100 的正整

数， 但是各个城市的编号未必连续。 文件里同一行中相邻的两个数都是用一个空白字符隔开的。

**输出格式：**

以一行的形式输出起点城市i 与终点城市 j 之间的最快路线所需要的时间。

## 输入输出样例 ##

**输入样例\#1：**  复制

0 1 0 0 0 0 0
    1 4
    4
    1 2 1
    1 3 1
    2 4 2
    3 4 3

**输出样例\#1：**  复制

啦啦，很水的spfa啦

#include<queue>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define N 10100
    #define maxn 9999999
    using namespace std;
    bool vis[N];
    queue<int>q;
    int n,m,x,y,z,s,e,tot;
    int f[N],w[N],to[N],dis[N],head[N],nextt[N];
    int h[8]={
           0,2,6,4,8,6,10,14};
    int read()
    {
        int x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9'){
           if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
        return x*f;
    }
    int add(int x,int y,int z)
    {
        ++tot;to[tot]=y,dis[tot]=z,nextt[tot]=head[x];head[x]=tot;
        ++tot;to[tot]=x,dis[tot]=z,nextt[tot]=head[y],head[y]=tot;
    }
    int spfa(int s)
    {
        for(int i=1;i<=n;i++) f[i]=maxn,vis[i]=0;
        f[s]=0,vis[s]=true,q.push(s);
        while(!q.empty())
        {
            x=q.front();q.pop();vis[x]=false;
            for(int i=head[x];i;i=nextt[i])
            {
                int t=to[i];
                if(f[t]>f[x]+dis[i])
                {
                    f[t]=f[x]+dis[i];
                    if(!vis[t]) vis[t]=true,q.push(t);
                }
            }
        }
    }
    int main()
    {
        for(int i=1;i<=7;i++) w[i]=read();
        s=read(),e=read();
        m=read();
        for(int i=1;i<=m;i++)
        {
            x=read(),y=read(),z=read();
            if(w[z]) z=h[z]/2;
            else z=h[z];
            add(x,y,z);
            n=max(n,max(x,y));
        }
        spfa(s);
        printf("%d",f[e]);
        return 0;
    }

转载于:https://www.cnblogs.com/z360/p/8227933.html

[1681.png]: /images/20210726/aa4b7f26f01340b19306a3c4d1988829.png