2019 寒假专题3 J、k、L题解

ACM

J-最短路径问题 (HDU-3790)

题意：

• 因为是中文题目应该很好理解，给出$n$个点，$m$条边，然后找出s到t的一条最短距离且最少花费的路线，最后输出最短距离和花费。

解题思路：

• 对于求两点的最短距离直接使用Dijkstra算法，对于如何求最少花费可以在对距离进行松弛操作时，对花费也进行松弛操作，最后在$d[v]==d[u]+g[v] [u]$时对v点的花费进行比较，如果比原花费小就更新即可。
• 最后要注意的是加边的可能会有重边，这时先比较边长度是否一致，不一致就比较大小，小的话就更新边长，如果边长度一致就开始比较花费，也是比较大小，小的话就更新花费。

代码：

#include<bits/stdc++.h>
//#include<iostream>
//#include<algorithm>
//#include<cmath>
//#include<cstring>
//#include<stdio.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e3+5;
const double eps=1e-4;
int g[N][N];
int d[N];
int va[N];
int val[N][N];
int vis[N];
//int pre[N];
void dijkstra(int s, int n)
{
    memset(d,inf,sizeof(d));
    memset(vis,0,sizeof(vis));
    memset(va,inf,sizeof(va));
    d[s]=0;
    va[s]=0;
//    pre[s]=0;
    while(1)
    {
        int v=-1;
        for(int u=1;u<=n;u++)
        {
            if(!vis[u]&&(v==-1||d[u]<d[v]))
                v=u;
        }
        if(v==-1)
            break;
        vis[v]=1;
        for(int u=1;u<=n;u++)
        {
            if(!vis[u]&&d[u]>d[v]+g[v][u])
            {
                d[u]=d[v]+g[v][u];
                va[u]=va[v]+val[v][u];
//                pre[u]=v; // 记录路径
            }
            else if(!vis[u]&&d[u]==d[v]+g[v][u])
                va[u]=min(va[u],va[v]+val[v][u]);
        }
    }
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)
            break;
        memset(g,inf,sizeof(g));
        memset(val,inf,sizeof(val));
        for(int i=0;i<m;i++)
        {
            int u,v,a,b;
            scanf("%d%d%d%d",&u,&v,&a,&b);
            if(g[u][v]>a)
            {
                g[u][v]=g[v][u]=a;
                val[u][v]=val[v][u]=b;
            }
            else if(g[u][v]==a)
                val[u][v]=val[v][u]=min(val[u][v],b);
        }
        int s,t;
        scanf("%d%d",&s,&t);
        dijkstra(s,n);
        printf("%d %d\n",d[t],va[t]);
    }
    return 0;
}

K-一个人的旅行 (HDU 2066)

题意：

• 中文题面应该很好理解，总的来说就是求他家到他某个想去的地方的最短时间（最短路）。

解题思路：

• 这道题需要注意的就是将他家视为$0$号点连接题目给出离他家最近那几个车站，然后跑最短路时注意把范围改成$0$到$N$就行了。最后比较他到每个他想去地方的最短时间，输出最短的那个时间即可。

代码：

#include<bits/stdc++.h>
//#include<iostream>
//#include<algorithm>
//#include<cmath>
//#include<cstring>
//#include<stdio.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e3+5;
const double eps=1e-4;
int g[N][N];
int d[N];
int vis[N];
//int pre[N];
void dijkstra(int s, int n)
{
    memset(d,inf,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[s]=0;
//    pre[s]=0;
    while(1)
    {
        int v=-1;
        for(int u=0;u<=n;u++)
        {
            if(!vis[u]&&(v==-1||d[u]<d[v]))
                v=u;
        }
        if(v==-1)
            break;
        vis[v]=1;
        for(int u=0;u<=n;u++)
        {
            if(!vis[u]&&d[u]>d[v]+g[v][u])
            {
                d[u]=d[v]+g[v][u];
//                pre[u]=v; // 记录路径
            }
        }
    }
}
int main()
{
    int t,n,m;
    while(~scanf("%d%d%d",&t,&n,&m))
    {
        int len=0;
        memset(g,inf,sizeof(g));
        for(int i=0;i<t;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            len=max(len,max(a,b));
            g[a][b]=g[b][a]=min(g[a][b],c);
        }
        for(int i=0;i<=len;i++)
            g[i][i]=0;
        for(int i=0;i<n;i++)
        {
            int a;
            scanf("%d",&a);
            g[0][a]=g[a][0]=0;
        }
        dijkstra(0,len);
        int ans=inf;
        for(int i=0;i<m;i++)
        {
            int a;
            scanf("%d",&a);
            ans=min(ans,d[a]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

L-HDU Today (HDU-2112)

题意：

• 题面中文应该很好理解，就是一个位置到另一个位置的最短路。

解题思路：

• 因为给出位置名都不是数字，所以可以$hash$一下，用数组或者是$map$都可以达到效果，然后直接用最短路算法跑即可。

代码：

#include<bits/stdc++.h>
//#include<iostream>
//#include<algorithm>
//#include<cmath>
//#include<cstring>
//#include<stdio.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e2+5;
const double eps=1e-4;
int g[N][N];
int d[N];
int vis[N];
//int pre[N];
void dijkstra(int s, int n)
{
    memset(d,inf,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[s]=0;
//    pre[s]=0;
    while(1)
    {
        int v=-1;
        for(int u=1;u<=n;u++)
        {
            if(!vis[u]&&(v==-1||d[u]<d[v]))
                v=u;
        }
        if(v==-1)
            break;
        vis[v]=1;
        for(int u=1;u<=n;u++)
        {
            if(!vis[u]&&d[u]>d[v]+g[v][u])
            {
                d[u]=d[v]+g[v][u];
//                pre[u]=v; // 记录路径
            }
        }
    }
}
map<string,int>q;
int main()
{
    int t;
    while(~scanf("%d",&t))
    {
        if(t==-1)
            break;
        q.clear();
        memset(g,inf,sizeof(g));
        int k=0;
        string s,tt;
        cin>>s>>tt;
        q[s]=++k;
        if(s!=tt)
            q[tt]=++k;
        for(int i=0;i<t;i++)
        {
            string a,b;
            int time;
            cin>>a>>b;
            if(q[a]==0)
                q[a]=++k;
            if(q[b]==0)
                q[b]=++k;
            scanf("%d",&time);
            g[q[a]][q[b]]=g[q[b]][q[a]]=time;
        }
        dijkstra(1,k);
        printf("%d\n",d[q[tt]]==inf?-1:d[q[tt]]);
    }
    return 0;
}