首页 > 代码库 > NYOJ 115 城市平乱

NYOJ 115 城市平乱

思路:最短路径算法

 

决心用这道题好好练练最短路径~

 

先附上flody算法,超时了

代码:

#include <iostream>#define INF 99999using namespace std;int e[1001][1001];//地图,邻接矩阵储存int N,M,P,Q;int n[101];//代表部队驻扎的点void flody();//flody算法int main(){    int res;    int num;    cin>>num;    int a,b,c;    while(num--)    {        res = INF;        //N表示部队数,M表示城市数,P表示城市之间的路的条数,Q表示发生暴乱的城市编号        cin>>N>>M>>P>>Q;                for(int i=1;i<=N;i++)        {            cin>>n[i];        }                //地图初始化        for(int i=1;i<=M;i++)        {            for(int j=1;j<=M;j++)            {                if(i==j)                    e[i][j] = 0;                else                {                    e[i][j] = INF;                }            }        }             for(int i=1;i<=P;i++)        {            cin>>a>>b>>c;            e[a][b] = c;            e[b][a] = c;        }                flody();                    for(int i=1;i<=N;i++)        {            res = min(e[Q][n[i]],res);        }                     cout<<res<<endl;    }    return 0;}//flody核心算法,估计超时。。void flody(){    for(int i=1;i<=M;i++)    {        for(int j=1;j<=M;j++)        {            for(int k=1;k<=M;k++)            {                if(e[j][k]>e[j][i]+e[i][k])                    e[j][k] = e[j][i]+e[i][k];            }        }    }}