题目描述

一个无向图，给出宁池晋的出发地点和目的地点，ss的出发地点和目的地地点，问你如果他俩都走最短路的情况下，最多可以有多少个相遇的地方。

样例

6 6
1 2 1
2 3 1
3 4 1
4 5 1
1 5 2
4 6 3
1 6 2 4
0 0

思想

无疑，两者最短路重叠部分一定是连续的，所以可以在floyd中维护该连续点集。

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1010,INF = 0x3f3f3f3f;
int p[N][N],d[N][N];
int n,m;
int t1,t2,t3,t4;

void init()
{
    for(int i = 1;i <= n;i++)
      for(int j = 1;j <= n;j++)
    {
      if(i == j) d[i][j] = 0;
      else
      {
          d[i][j] = INF;
      }
      p[i][j] = 0;
    }
}

void floyd()
{
    for(int k = 1;k <= n;k++)
      for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
    {
        if(d[i][j] > d[i][k] + d[k][j])
        {
            d[i][j] = d[i][k] + d[k][j];
            p[i][j] = p[i][k] + p[k][j];
        }
        else if(d[i][j] == d[i][k] + d[k][j])
        {
            p[i][j] = max(p[i][j],p[i][k] + p[k][j]);
        }
    }
}

int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        init();
        if(n == 0 && m == 0)
        {
            break;
        }
        for(int i = 1;i <= m;i++)
        {
            int a,b,c;
            cin >> a >> b >> c;
            if(d[a][b] > c)
            {
                d[a][b] = d[b][a] = c;
                p[a][b] = p[b][a] = 1;
            }
        }
        cin >> t1 >> t2 >> t3 >> t4;
        floyd();
        int ans = -1;
          for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
        {
            if(p[i][j] > ans)
            {
                if((d[t1][t2] == d[t1][i] + d[i][j] + d[j][t2]) && (d[t3][t4] == d[t3][i] + d[i][j] + d[j][t4]))
                {
                    ans = p[i][j];
                }
            }
        }
        cout << ans + 1 << endl;
    }
}