本文共 2065 字，大约阅读时间需要 6 分钟。
今天做了两道dijkstra算法的基础题;题目都没有什么难度,基本上就是直接套dijkstra算法的代码就行了。
但还是有一些注意的事项，也是今天犯过错的地方：
1是用基本版dijkstra解题的时候要记得给邻接矩阵初始化；
2.是用队列优化的dijkstra的时候记得数组大下必须取顶点数和边数中的大值；
3是用注意题目中给的图是有向图还是无向图,并注意邻接表标示图时无向图的输入及相应算法中边数多少的改变；
4题目中可能会给出重边的情况，这种情况对用基于邻接表的算法没有影响,但对于基于邻接矩阵的算法就要在输入的时候就要注意判断
对于一条边多次输入的情况我们取其最小的权值。
两道题的代码如下：
poj 2387
#include #include #include using namespace std; #define INF 1<<30#define Max 2010 int map[Max][Max],n,m;int visited[Max],d[Max];void Init(){ for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) map[i][j]=INF; map[i][i]=0; }}void dijkstra(int s){ int i,j,k; memset(visited,0,sizeof(visited)); for(i=1;i<=n;i++) d[i]=map[s][i]; visited[s]=1; for(i=0;i d[mini]+map[mini][j]) d[j]=d[mini]+map[mini][j]; }}int main(){ int i,j,k; while(cin>>m>>n) //注意题目先输入的是边数。。。。。。 { Init(); for(i=0;i >a>>b>>c; if(map[a][b]>c) //这种题目一般都有重边的陷阱 { map[a][b]=c; map[b][a]=c; } } dijkstra(n); cout< <
hdu 1874
#include #include #include #include #include using namespace std;#define INF 10000000#define Max 1010int u[Max],v[Max],w[Max],visited[Max];int first[Max],next[Max],d[Max],n,m,e;typedef pair pii;priority_queue ,greater >q;void dijkstra(int s){ int i,j,k; memset(visited,0,sizeof(visited)); for(i=0;i d[q.top().second]) q.pop(); if(q.empty()) break;*/ pii u1=q.top(); q.pop(); int x=u1.second; if(visited[x]) continue; visited[x]=1; for(int e=first[x];e!=-1;e=next[e]) if(d[v[e]]>d[x]+w[e]) { d[v[e]]=d[x]+w[e]; q.push(make_pair(d[v[e]],v[e])); } }}void add_e(int a,int b,int c){ u[e]=a;v[e]=b; next[e]=first[a]; w[e]=c; first[a]=e++;}int main(){ int i,j,k1,k2,w; while(cin>>n>>m) { memset(first,-1,sizeof(first)); e=0; for(int k=0;k >k1>>k2>>w; add_e(k1,k2,w); add_e(k2,k1,w); } cin>>k1>>k2; dijkstra(k1); if(d[k2]>=INF) cout<<"-1"<
转载地址：http://hhefb.baihongyu.com/