p3905题解

xiaolou · 2018-10-13 21:57:26 · 题解

2325131433448687~

这道题居然没有floyd的题解，蒟蒻表示愤愤不平，100的数据都没人写floyd，那我就来水一发2333。。。

神奇代码：

#include <bits/stdc++.h>

using namespace std;
int h[105][105],d[105][105];
void floyd(int n)
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                h[i][j]=min(h[i][j],h[i][k]+h[k][j]);
}//floyd的板子，floyd的特点就是思路清晰，代码精简，所以很适合我这样听不懂dijkstra和spfa的蒟蒻使用。。。    

int main()
{
    memset(h,0x3f3f3f3f,sizeof(h));//一拜初始化
    int n,m,k;
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int s,e;
        cin >> s >> e;
        cin >> d[s][e];
        d[e][s]=d[s][e];
        h[s][e]=h[e][s]=0;
    }//二拜建图（注意是双向边，建成单向边会瞬间爆炸。。。）
    cin >> k;
    for(int i=1;i<=k;i++)
    {
        int s,e;
        cin >> s >> e;
        h[s][e]=h[e][s]=d[s][e];//三拜删边(2333)
    }
    floyd(n);//套板子喽！真香。。。
    int st,en;
    cin >> st >> en;
    cout << h[st][en];//愉快地输出，最后祝大家NOIP进复赛！
    return 0;
    //2325131433448687
}