题解 | #双重最短路#

双重最短路

https://ac.nowcoder.com/acm/problem/21736

  • 此题dijkstra,spfa,Floyd都可以过.
  • 但是我第一次是用的Floyd
  • 因为此题n范围非常小,即使是O(n^3)的Floyd算法也不会超时,而且Floyd写起来简单,只有4行代码
    Floyd代码:
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=30,INF=0x3f3f3f3f;
int w1[N][N],w2[N][N];
int d1[N],d2[N];
char s1[N][N];
char s2[N][N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        scanf("%s",s1[i]);
    for(int i=0;i<n;i++)
        scanf("%s",s2[i]);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
          if(s1[i][j]=='.')
           w1[i][j]=INF;
           else w1[i][j]=s1[i][j]-'0';

           if(s2[i][j]=='.')
           w2[i][j]=INF;
           else w2[i][j]=s2[i][j]-'0';

        }
    }
    for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    w1[i][j]=min(w1[i][j],w1[i][k]+w1[k][j]);

    for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    w2[i][j]=min(w1[i][j],w1[i][k]+w1[k][j]);

     if(w1[0][1]==INF||w2[0][1]==INF)
        cout<<-1;
    else
        cout<<w1[0][1]*w2[0][1];

}

spfa算法代码:

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=30,INF=0x3f3f3f3f;
int w1[N][N],w2[N][N];
int d1[N],d2[N];
bool st1[N],st2[N];
char s1[N][N];
char s2[N][N];

void spfa1()
{    
    memset(d1,0x3f,sizeof d1);
    queue<int> q1;
    d1[0]=0;
    q1.push(0);
    while(q1.size())
    {
        int t=q1.front();
        q1.pop();
        st1[t]=false;
        for(int i=0;i<n;i++)
        {
        if(d1[i]>d1[t]+w1[t][i])
        {
            d1[i]=d1[t]+w1[t][i];
            if(!st1[i])
            {
                st1[i]=true;
                q1.push(i);
            }
        }
          }
    }
}
void spfa2()
{

     memset(d2,0x3f,sizeof d2);
     queue<int>q2;
    d2[0]=0; 
      q2.push(0);
    while(q2.size())
    {
        int t=q2.front();
        q2.pop();
        st2[t]=false;
        for(int i=0;i<n;i++)
        {
            if(d2[i]>d2[t]+w2[t][i])
            {
               d2[i]=d2[t]+w2[t][i];
                if(!st2[i])
                {
                    st2[i]=true;
                    q2.push(i);
                }
            }
        }
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        scanf("%s",s1[i]);
    for(int i=0;i<n;i++)
        scanf("%s",s2[i]);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
          if(s1[i][j]=='.')
           w1[i][j]=INF;
           else w1[i][j]=s1[i][j]-'0';

           if(s2[i][j]=='.')
           w2[i][j]=INF;
           else w2[i][j]=s2[i][j]-'0';

        }
    }
    spfa1(); spfa2();
     if(d1[1]==INF||d2[1]==INF)
        cout<<-1;
    else
        cout<<d1[1]*d2[1];

}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-14 18:10
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-27 14:49
韶关学院_2022
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议