好贷网好贷款

nyoj 115

发布时间:2016-12-3 6:20:18 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"nyoj 115",主要涉及到nyoj 115方面的内容,对于nyoj 115感兴趣的同学可以参考一下。

城市平乱 时间限制: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 数据保证暴乱的城市是可达的。输出对于每组测试数据,输出第一支部队到达叛乱城市时的时间。每组输出占一行样例输入 1 3 8 9 8 1 2 3 1 2 1 2 3 2 1 4 2 2 5 3 3 6 2 4 7 1 5 7 3 5 8 2 6 8 2 样例输出 4 代码:   #include<stdio.h> #include<string.h> #include<stdlib.h> #define INT 9999999int N,M,P,Q,a,b,t; int final[1010]; int map[1010][1010]; int D[1010]; int num[110],ans[110];int cmp(const void *a,const void *b) {  return *(int *)a-*(int *)b; } void Dijkstra(int v) {  int i,j,pos,min;  memset(final,0,sizeof(final));  for(i=1;i<=M;i++)   D[i]=map[v][i];  final[v]=1;  for(i=1;i<=M;i++)  {   min=INT;   for(j=1;j<=M;j++)   {    if(!final[j] && D[j]<min)    {     min=D[j];     pos=j;    }   }   final[pos]=1;   for(j=1;j<=M;j++)   {    if(!final[j] && map[pos][j]<INT)    {     if(D[pos]+map[pos][j]<D[j])      D[j]=D[pos]+map[pos][j];    }   }  } }int main() {  int T,i,j;  scanf("%d",&T);  while(T--)  {   scanf("%d %d %d %d",&N,&M,&P,&Q);   for(i=1;i<=M;i++)   {//初始化    for(j=1;j<=M;j++)    {     if(i==j)      map[i][j]=0;     else      map[i][j]=INT;    }   }   for(i=0;i<N;i++)    scanf("%d",&num[i]);   for(i=1;i<=P;i++)   {//输入边    scanf("%d %d %d",&a,&b,&t);    if(t<map[a][b] || t<map[b][a])    {     map[a][b]=t;     map[b][a]=t;    }   }   for(i=0;i<N;i++)   {    Dijkstra(num[i]);    ans[i]=D[Q];   }   qsort(ans,N,sizeof(ans[0]),cmp);   printf("%d\n",ans[0]);  }  return 0; }       

上一篇:SQLite使用
下一篇:异步通知

相关文章

关键词: nyoj 115

相关评论