题解 | #双重最短路#

• 此题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];

}