当前位置: 代码迷 >> 综合 >> hdu 2112 HDU Today Dijkstra算法
  详细解决方案

hdu 2112 HDU Today Dijkstra算法

热度:10   发布时间:2023-12-05 14:00:37.0

这道题关键在于字符串怎么转变成数字,我这里是用字符型二维数组进行处理,写出一个change函数用来返回字符串在数组里面存放的位置,之后就是典型的Dijkstra算法了。

附代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
#define INF 1<<25
using namespace std;
int vis[160000];
const int N = 160;
int dis[N][N], mini[N], m;
char add[N][40];void Init(){for(int i=0;i<160;i++){for(int j=0;j<160;j++){if(i==j){dis[i][j]=0;}else{dis[i][j]=INF;}}}
}
int change(char *str){int i;for(i=0;i<m;i++){if(strcmp(add[i],str)==0){return i;}}if(i==m){strcpy(add[i],str);m++;return m-1;}
}
void dij(){memset(vis,0,sizeof(vis));for(int i=0;i<m;i++){mini[i]=dis[0][i];vis[i]=1;}vis[0]=0;for(int i=0;i<m;i++){int mi=INF,mj;for(int j=0;j<m;j++){if(vis[j]&&mini[j]<mi){mi=mini[j];mj=j;}}if(mi==INF) break;vis[mj]=0;for(int j=0;j<m;j++){if(vis[j]&&mini[j]>mini[mj]+dis[mj][j]){mini[j]=mini[mj]+dis[mj][j];}}//while(1){};}
}int main()
{int n;while(~scanf("%d",&n)&&n!=-1){Init();char st[40], ed[40], s1[40], s2[40];int a, b, c;scanf("%s%s",st, ed);strcpy(add[0], st);strcpy(add[1], ed);m = 2;int i,j;for(i = 0; i < n; i++){scanf("%s%s%d",s1, s2, &c);a = change(s1);b = change(s2);dis[a][b] = dis[b][a] = c;}if(strcmp(st, ed) == 0){printf("0\n");continue;}// Dijkstra();dij();/* for(int i=0;i<m;i++){cout<<i<<" "<<mini[i]<<endl;}*/if(mini[1]==INF)cout<<"-1"<<endl;elsecout<<mini[1]<<endl;}return 0;
}

  相关解决方案