本文主要是介绍poj1062-dijkstra算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
题目分析：
最短路径，用dijkstra算法可一个实现。就是多了限制条件。
用枚举方法。
代码;
#include<stdio.h>
#include<cstring> #define max 1000000
int n,m;
int graph[105][105];
int value[105],level[105],d[105];
bool used[105],limit[105];int dijkstra()
{int sum=max;int i,j;int k,dis;memset(used,0,sizeof(used));d[1]=0; //把起点初始化为零，符合实际。 for(i=2;i<=n;i++) //把未加入的点，赋值为无穷大，合理！ d[i]=max;for(i=1;i<=n;i++){k=0;dis=max;for(j=1;j<=n;j++)if(!used[j]&&d[j]<=dis&&limit[j]) //选取最小的点。 {k=j;dis=d[j];}used[k]=true; //标记选取的点 for(j=1;j<=n;j++){if(limit[j]&&d[j]>d[k]+graph[k][j]) //更新当前最短路 d[j]=d[k]+graph[k][j];}}for(i=1;i<=n;i++){d[i]+=value[i];if(d[i]<sum)sum=d[i];}return sum;
}
int main()
{int i,j,t,v,x,res=max;scanf("%d%d",&m,&n);for(i=0;i<=n;i++)for(j=0;j<=n;j++)if(i==j)graph[i][j]=0;else graph[i][j]=max;for(i=1;i<=n;i++){scanf("%d%d%d",&value[i],&level[i],&x);for(j=1;j<=x;j++){scanf("%d%d",&t,&v);graph[i][t]=v;}}for(i=0;i<=m;i++){memset(limit,0,sizeof(limit));for(j=1;j<=n;j++)if(level[j]>=level[1]-m+i&&level[j]<=level[1]+i) //枚举 limit[j]=true;t=dijkstra();if(res>t)res=t;}printf("%d\n",res);return 0;
}这篇关于poj1062-dijkstra算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
