首页 > 代码库 > nyoj 115------城市平乱（ dijkstra // bellman ）
nyoj 115------城市平乱（ dijkstra // bellman ）
城市平乱
时间限制：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
- 来源
- 《世界大学生程序设计竞赛高级教程·第一册》改编
- 代码：
- 运用最简单的邻接矩阵+狄斯喹诺算法来做题目
- 代码为：
-
View Code1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<iostream> 5 using namespace std; 6 const int maxn=1002; 7 const int inf=0x3f3f3f3f; 8 int cost[maxn][maxn]; 9 int path[maxn],lowc[maxn];10 bool vis[maxn];11 void Dijkstra(int n,int st)12 {13 int i,j,minc;14 memset(vis,0,sizeof(vis));15 vis[st]=1 ;16 for(i=0;i<n;i++)17 {18 lowc[i]=cost[st][i];19 path[i]=st;20 }21 lowc[st]=0;22 path[st]=-1; //树根的标记23 int pre=st;24 for(i=1;i<n;i++)25 {26 minc=inf;27 for(j=0;j<n;j++)28 {29 if(vis[j]==0&&lowc[pre]+cost[pre][j]<lowc[j])30 {31 lowc[j]=lowc[pre]+cost[pre][j];32 path[j]=pre;33 }34 }35 for(j=0;j<n;j++)36 {37 if(vis[j]==0&&lowc[j]<minc)38 {39 minc=lowc[j];40 pre=j;41 }42 }43 vis[pre]=1;44 }45 }46 int groop[105];47 int main()48 {49 int n,m,p,q,i,j;50 int a,b,c,test,res;51 // freopen("test.in","r",stdin);52 scanf("%d",&test);53 while(test--)54 {55 scanf("%d%d%d%d",&n,&m,&p,&q);56 for(i=0;i<n;i++)57 scanf("%d",&groop[i]);58 for(i=0;i<m;i++)59 for(j=0;j<m;j++)60 cost[i][j]=inf;61 for(i=0;i<p;i++)62 {63 scanf("%d%d%d",&a,&b,&c);64 a-- , b-- ;65 if(cost[a][b]>c||cost[a][b]==0)66 cost[a][b]=cost[b][a]=c;67 }68 Dijkstra(m,q-1);69 res=inf;70 for(i=0;i<n;i++)71 {72 if(res>lowc[groop[i]-1])73 res=lowc[groop[i]-1];74 }75 printf("%d\n",res);76 }77 return 0;78 }
采用bellman算法求最短路 裸的算法
代码：
View Code1 /*bellman求最短路*/ 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<iostream> 7 using namespace std; 8 9 const int inf=0x3f3f3f3f;10 int m,n,p,q,pre[1005],edge[200005][3];11 int dist[1005];12 13 int relax(int u ,int v ,int c)14 {15 if(dist[v]>dist[u]+c)16 {17 dist[v]=dist[u]+c;18 pre[v]=u;19 return 1;20 }21 return 0;22 }23 24 int bellman(int st)25 {26 int i,j;27 for(i=1;i<=m;i++){28 dist[i]=inf;29 pre[i]=-1;30 }31 dist[st]=0;32 bool flag;33 for(i=1;i<m;i++)34 {35 flag=false; //优化36 for(j=1;j<=2*p;j++)37 {38 if(1==relax(edge[j][0],edge[j][1],edge[j][2]))39 flag=true;40 }41 if(!flag) break;42 }43 for(j=1;j<=2*p;j++)44 {45 if(1==relax(edge[j][0],edge[j][1],edge[j][2]))46 return 0; //有负圈47 }48 return 1;49 }50 int groop[105];51 int main()52 {53 int test,i,j;54 // freopen("test.in","r",stdin);55 scanf("%d",&test);56 while(test--)57 {58 scanf("%d%d%d%d",&n,&m,&p,&q);59 for(i=0;i<n;i++)60 scanf("%d",&groop[i]);61 for(i=1;i<=p;i++)62 {63 //建立无向图64 scanf("%d%d%d",&edge[i][0],&edge[i][1],&edge[i][2]);65 edge[p+i][0]=edge[i][1];66 edge[p+i][1]=edge[i][0];67 edge[p+i][2]=edge[i][2];68 }69 bellman(q);70 int res=inf;71 for(i=0;i<n;i++)72 {73 if(res>dist[groop[i]])74 res=dist[groop[i]];75 }76 printf("%d\n",res);77 }78 return 0;79 }
- 套用模板居然错了，还有比这更扯的嘛!!!
- 邻接表+狄斯喹诺算法
- RuntimeError
- View Code
1 /*狄斯喹诺算法*/ 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<iostream> 7 #include<queue> 8 #include<vector> 9 #pragma comment(linker, "/STACK:102400000,102400000") 10 11 const int inf=0x3f3f3f3f; 12 using namespace std ; 13 14 int cost[100005],dist[1005]; 15 int e,pnt[100005],next[100005],head[1005],prev[1005],vis[1005]; 16 int groop[105]; 17 18 struct node 19 { 20 int v,c; 21 node ( int vv=0 , int cc=0 ) : v(vv),c(cc){} 22 bool operator < ( const node &r ) const 23 { 24 return c>r.c ; 25 } 26 }; 27 28 void dijkstra (int n ,const int src) 29 { 30 node mv; 31 int i,j,k,pre; 32 priority_queue<node> que; 33 vis[src]=1; 34 dist[src]=0; 35 que.push(node(src,0)); 36 for(pre=src,i=1;i<n;i++) 37 { 38 for(j=head[pre];j!=-1;j=next[j]) 39 { 40 k=pnt[j]; 41 if(vis[k]==0&&dist[pre]+cost[j]<dist[k]) 42 { 43 dist[k]=dist[pre]+cost[k]; 44 que.push(node(pnt[j] , dist[k])); 45 prev[k]=pre; 46 } 47 } 48 49 while(!que.empty()&&vis[que.top().v]==1) 50 que.pop(); 51 if(que.empty()) break; 52 mv=que.top(); 53 que.pop(); 54 vis[mv.v]=1; 55 pre=mv.v; 56 57 } 58 } 59 60 inline void addedge(int u , int v , int c) 61 { 62 //面对重边又该怎么办 63 64 pnt[e]=v; 65 cost[e]=c; 66 next[e]=head[u]; 67 head[u]=e++; 68 } 69 70 void init(int nv ,int ne) 71 { 72 int i,u,v,c; 73 e=0; 74 memset( head , -1 , sizeof(head) ); 75 memset( vis , 0 , sizeof(vis) ); 76 memset( prev , -1 , sizeof(prev) ); 77 memset(pnt,0,sizeof(pnt)); 78 for(i=0;i<nv;i++) 79 dist[i]=inf; 80 // 如 何 应 对 重 边 81 for(i=0;i<ne;i++) 82 { 83 scanf("%d%d%d",&u,&v,&c); 84 u-- ; 85 v-- ; 86 addedge(u,v,c); 87 addedge(v,u,c); 88 } 89 } 90 91 int main() 92 { 93 int test,i; 94 int n,m,p,q; 95 scanf("%d",&test); 96 while(test--) 97 { 98 memset(cost,-1,sizeof(cost)); 99 scanf("%d%d%d%d",&n,&m,&p,&q);100 for(i=0;i<n;i++)101 scanf("%d",&groop[i]);102 init(p,p);103 dijkstra(n,q-1);104 int res=inf;105 for(i=0;i<n;i++)106 if(res>dist[groop[i]-1])107 res=dist[groop[i]-1];108 printf("%d\n",res);109 } 110 return 0;111 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。