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

NYOJ-115 城市平乱

2024-11-04 02:45:02   205人阅读

                                                     城市平乱

时间限制：1000 ms  |  内存限制：65535 KB
难度：4
描述

南将军统领着N个部队，这N个部队分别驻扎在N个不同的城市。

他在用这N个部队维护着M个城市的治安，这M个城市分别编号从1到M。

现在，小工军师告诉南将军，第K号城市发生了暴乱，南将军从各个部队都派遣了一个分队沿最近路去往暴乱城市平乱。

现在已知在任意两个城市之间的路行军所需的时间，你作为南将军麾下最厉害的程序员，请你编写一个程序来告诉南将军第一个分队到达叛乱城市所需的时间。

技术分享

注意，两个城市之间可能不只一条路。

输入
第一行输入一个整数T，表示测试数据的组数。(T<20)
每组测试数据的第一行是四个整数N,M,P,Q(1<=N<=100,N<=M<=1000,M-1<=P<=100000)其中N表示部队数，M表示城市数，P表示城市之间的路的条数,Q表示发生暴乱的城市编号。
随后的一行是N个整数，表示部队所在城市的编号。
再之后的P行，每行有三个正整数，a,b,t(1<=a,b<=M,1<=t<=100)，表示a,b之间的路如果行军需要用时为t

数据保证暴乱的城市是可达的。
输出
对于每组测试数据，输出第一支部队到达叛乱城市时的时间。每组输出占一行
样例输入
13 8 9 81 2 31 2 12 3 21 4 22 5 33 6 24 7 15 7 35 8 26 8 2
样例输出
4
 

这是一道非常经典的图论最短路问题！试了4种解法（Bellman-Ford，Dijkstra，Spfa，Floyd-Warshall超时）

 

1.Bellman-Ford

Bellman-Ford最重要的一个特点就是可以判负圈，如果图中不存在从s可达的负圈，那么最短路不会经过同一个顶点两次（也就是说最多通过M-1条边），while（true）的循环最多执行M-1次，如果存在从s可达的负圈，那么在第M次循环中也会更新d的值，因此可以检查负圈。

 

01.   

02.#include<iostream>
03.#include<cstring>
04.usingnamespace std;
05.  
06.constint INF=0x7fffffff; 
07.intT,N,M,P,Q;
08.intd[1005],g[105];
09.  
10.structedge
11.{
12.    intfrom,to,cost;
13.}es[200010];
14.  
15.intbellman(int s) 
16.{
17.    for(inti=0;i<=M;i++)
18.        d[i]=INF;   
19.    d[s]=0;
20.    while(true)
21.    {
22.        boolupdate=false;
23.        for(inti=0;i<2*P;i++)
24.        {
25.            edge e=es[i];
26.            if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost)
27.            {
28.                d[e.to]=d[e.from]+e.cost;
29.                update=true;
30.            }
31.        }
32.        if(!update)
33.            break;
34.    }
35.} 
36.  
37.boolloop()
38.{//判负圈 
39.    for(inti=0;i<M;i++)
40.        for(intj=0;j<2*P;j++)
41.        {
42.            edge e=es[j];
43.            if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost)
44.            {
45.                d[e.to]=d[e.from]+e.cost;
46.                if(i==M-1)
47.                    returntrue;
48.            }
49.        }
50.    returnfalse;
51.} 
52.  
53.intmain()
54.{
55.    cin>>T;
56.    while(T--)
57.    {
58.        cin>>N>>M>>P>>Q;
59.        for(inti=0;i<N;i++)
60.            cin>>g[i];
61.        for(inti=0;i<P;i++)
62.        {
63.            cin>>es[i].from>>es[i].to>>es[i].cost;
64.            es[i+P].from=es[i].to;//以Q为出发点反向建立邻接表 
65.            es[i+P].to=es[i].from;
66.            es[i+P].cost=es[i].cost;            
67.        }       
68.        bellman(Q);
69.        intres=INF;
70.        for(inti=0;i<N;i++)
71.            if(res>d[g[i]])
72.                res=d[g[i]];
73.        cout<<res<<endl;        
74.    }
75.    return0;
76.}


 

 

2.Dijkstra

Dijkstra算法就是先找到最短距离已经确定的顶点，从它出发更新相邻顶点的最短距离。

 

01.   

02.#include<iostream>
03.#include<cstring>
04.#include<algorithm>
05.usingnamespace std;
06.  
07.constint INF=1000000; 
08.intT,N,M,P,Q;
09.intd[1005],g[105];
10.intcost[1005][1005];
11.boolused[1005];
12.  
13.voiddijkstra(int s) 
14.{
15.    for(inti=0;i<=M;i++)
16.    {
17.        d[i]=INF;
18.        used[i]=false;
19.    }   
20.    d[s]=0;
21.    while(true)
22.    {
23.        intk=-1;
24.        for(inti=1;i<=M;i++)
25.            if(!used[i] && (k==-1 || d[i]<d[k]))
26.                k=i;
27.        if(k==-1)
28.            break; 
29.        used[k]=true;
30.        for(inti=1;i<=M;i++)
31.            d[i]=min(d[i],d[k]+cost[k][i]); 
32.    }   
33.} 
34.  
35.intmain()
36.{
37.    cin>>T;
38.    while(T--)
39.    {
40.        cin>>N>>M>>P>>Q;
41.        for(inti=0;i<N;i++)
42.            cin>>g[i];
43.        for(inti=0;i<1005;i++)
44.            for(intj=0;j<1005;j++)
45.                cost[i][j]=INF;
46.        for(inti=0;i<P;i++)
47.        {
48.            intx,y,z;
49.            cin>>x>>y>>z;
50.            cost[x][y]=z;//邻接矩阵 
51.            cost[y][x]=z;           
52.        }
53.        dijkstra(Q);
54.        intres=INF;
55.        for(inti=0;i<N;i++)
56.            if(res>d[g[i]])
57.                res=d[g[i]];
58.        cout<<res<<endl;    
59.    }
60.    return0;
61.}


使用堆优化后，速度和内存会减少很多

 

01.   

02.#include<iostream>
03.#include<cstring>
04.#include<vector>
05.#include<queue>
06.usingnamespace std;
07.  
08.constint INF=1000000; 
09.intT,N,M,P,Q;
10.intd[1005],g[105];
11.typedefpair<int,int> pa;
12.  
13.structedge{
14.    intto,cost;
15.};
16.vector<edge> v[1005];
17.  
18.voiddijkstra(int s) 
19.{   
20.    priority_queue<pa,vector<pa>,greater<pa> > que;
21.    memset(d,INF,sizeof(d));
22.    d[s]=0;
23.    que.push(pa(0,s));
24.    while(!que.empty())
25.    {
26.        pa pai=que.top();
27.        que.pop();
28.        intk=pai.second;
29.        if(d[k]<pai.first) 
30.            continue;
31.        for(inti=0;i<v[k].size();i++)
32.        {
33.            edge e=v[k][i];
34.            if(d[e.to]>d[k]+e.cost)
35.            {
36.                d[e.to]=d[k]+e.cost;
37.                que.push(pa(d[e.to],e.to));
38.            }
39.        }
40.    }
41.} 
42.  
43.intmain()
44.{
45.    cin>>T;
46.    while(T--)
47.    {
48.        cin>>N>>M>>P>>Q;
49.        memset(v,0,sizeof(v));
50.        for(inti=0;i<N;i++)
51.            cin>>g[i];
52.        for(inti=0;i<P;i++)
53.        {
54.            edge e;
55.            intx,y,z;
56.            cin>>x>>y>>z;
57.            e.to=y;
58.            e.cost=z;//邻接表
59.            v[x].push_back(e);
60.            e.to=x;
61.            v[y].push_back(e);      
62.        }
63.        dijkstra(Q);
64.        intres=INF;
65.        for(inti=0;i<N;i++)
66.            if(res>d[g[i]])
67.                res=d[g[i]];
68.        cout<<res<<endl;    
69.    }
70.    return0;
71.}


 

 

3.Spfa

Spfa是Bellman-Ford算法的一种队列优化实现，减少了不必要的计算

 

01.   
02.#include<iostream>
03.#include<algorithm>
04.#include<cstring>
05.#include<queue>
06.usingnamespace std;
07.  
08.constint INF=1000000; 
09.intT,N,M,P,Q;
10.intd[1005],g[105],cost[1005][1005];
11.boolused[1005];
12.  
13.intspfa(int s)
14.{
15.     memset(d,INF,sizeof(d));
16.     memset(used,0,sizeof(used));
17.     queue<int> que;
18.     d[s]=0;
19.     used[s]=true;
20.     que.push(s);
21.     while(!que.empty())
22.     {
23.         intk=que.front();
24.         que.pop();
25.         for(inti=0;i<M;i++)
26.         {//存在负权时当某点的入队次数超过顶点数返回
27.            if(d[i]>d[k]+cost[k][i])
28.            {
29.               d[i]=d[k]+cost[k][i];
30.               if(!used[i])
31.               {
32.                    que.push(i);
33.                    used[i]=true;    
34.               }        
35.            }            
36.         }
37.        used[k]=false;            
38.    }    
39.} 
40.  
41.intmain()
42.{
43.    cin>>T;
44.    while(T--)
45.    {
46.        cin>>N>>M>>P>>Q;
47.        for(inti=0;i<=M;i++)
48.            for(intj=0;j<=M;j++)
49.                cost[i][j]=INF;
50.        for(inti=0;i<N;i++)
51.            cin>>g[i];
52.        for(inti=0;i<P;i++)
53.        {
54.            intx,y,z;
55.            cin>>x>>y>>z;
56.            cost[x][y]=z;
57.            cost[y][x]=z;   
58.        }
59.        spfa(Q);
60.        intres=INF;
61.        for(inti=0;i<N;i++)         
62.            if(res>d[g[i]])
63.                res=d[g[i]];
64.        cout<<res<<endl;    
65.    }
66.    return0;
67.}


 

4.Floyd-Warshall

Floyd-Warshall使用的是动态规划的思想，不过复杂度比较大，如果对复杂度要求不高的情况下还是很方便的。

代码超时：

 

01.   

02.#include<iostream>
03.#include<algorithm>
04.#include<cstring>
05.usingnamespace std;
06.  
07.constint INF=1000000; 
08.intT,N,M,P,Q;
09.intd[1005][1005],g[105];
10.  
11.voidfloyd() 
12.{   
13.    for(intk=1;k<=M;k++)
14.        for(inti=1;i<=M;i++)
15.            for(intj=1;j<=M;j++)
16.                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
17.} 
18.  
19.intmain()
20.{
21.    cin>>T;
22.    while(T--)
23.    {
24.        cin>>N>>M>>P>>Q;
25.        for(inti=0;i<=M;i++)
26.            for(intj=1;j<=M;j++)
27.                if(i==j)
28.                    d[i][j]=0;
29.                else
30.                    d[i][j]=INF;
31.        for(inti=0;i<N;i++)
32.            cin>>g[i];
33.        for(inti=0;i<P;i++)
34.        {
35.            intx,y,z;
36.            cin>>x>>y>>z;
37.            d[x][y]=z;
38.            d[y][x]=z;  
39.        }
40.        floyd();
41.        intres=INF;
42.        for(inti=0;i<N;i++)         
43.            if(res>d[Q][g[i]])
44.                res=d[Q][g[i]];
45.        cout<<res<<endl;    
46.    }
47.    return0;
48.}


 

NYOJ-115 城市平乱


联系
我们