hdu 2544 最短路题解（dijkstra/迪杰斯特拉算法）

题目链接：?pid=2544

这道题用dijkstra模板一套就出来了。

模板：

需要注意的是，这里的边应该是双向边，，所以在输入边的数据的时候应该这样写：

for(i=0;i<m;i++){scanf("%d%d%d",&a,&b,&c);g.map[a][b]=g.map[b][a]=c;}

我就是这里错了所以样例都过不了，后来一问才发现的。

代码：

#include <iostream>#include <cstdio>#include <cstring>#define N 110using namespace std;typedef struct node {int map[N][N];//邻接矩阵int n;//顶点数int m;//边数}MGragh;void dijkstra(int *pre,int *dis,MGragh g,int v0){int vis[g.n+1];int i,j,k;memset(vis,0,sizeof(vis));for(i=1;i<=g.n;i++){if(g.map[v0][i]>0&&i!=v0){dis[i]=g.map[v0][i];pre[i]=v0;}else {dis[i]=INT_MAX;pre[i]=-1;}vis[i]=false;dis[v0]=0;pre[v0]=v0;}vis[v0]=true;for(i=1;i<=g.n;i++){int min=INT_MAX;int u;for(j=1;j<=g.n;j++){if(min>dis[j]&&vis[j]==false){min=dis[j];u=j;}}vis[u]=true;for(k=1;k<=g.n;k++){if(vis[k]==false&&g.map[u][k]>0&&g.map[u][k]+min<dis[k]){dis[k]=g.map[u][k]+min;pre[k]=u;}}}}int main(){int i,j,a,b,c;int n,m;while(scanf("%d%d",&n,&m)&&n+m>0){MGragh g;g.n=n;//初始化g.m=m;int pre[n+1];int dis[n+1];for(i=0;i<N;i++){for(j=0;j<N;j++){g.map[i][j]=0;}}memset(pre,0,sizeof(pre));memset(dis,0,sizeof(dis));for(i=0;i<m;i++){scanf("%d%d%d",&a,&b,&c);g.map[a][b]=g.map[b][a]=c;}dijkstra(pre,dis,g,1);printf("%d\n",dis[n]);}return 0;}

当你能爱的时候就不要放弃爱

相关文章：

你感兴趣的文章：

标签云：