图论中最短路问题,太久没看,竟然把算法忘了。今天复习了一下(用我自己写的项目论文),其实思想很简单的,以后比赛要是怕忘记,就把算法整理好带去得了。
比赛前是随便弄一段以前写的最短路代码带去现场的,结果不会用,折腾了半天才搞出来。这次吸取教训,把模板的衔接性写好一点,同时我把Dijkstra()故意改的特别短,这样做模板方便,抄的快啊。
#include <iostream> using namespace std; #define MAXN 50 // 题目可能出现的最大顶点数 #define Inf 100000 void GetData(int arcs[][MAXN], int & N) { int i, j; cin >> N; for(i=0; i<N-1; i++) { arcs[i][i] = Inf; for(j=i+1; j<N; j++) { cin >> arcs[i][j]; arcs[j][i] = arcs[i][j]; } } arcs[i][i] = Inf; } // 下标均从0开始计,N为顶点总数+1 // 简称arcs->a, dist->d, visited->v. int Dijkstra(int a[][MAXN],int N,int v1,int v2) { int i, p, d[MAXN], t=Inf; bool v[MAXN]={0}; for(v[v1]=1,i=0;i<N;i++) d[i]=a[v1][i]; // 给dist赋值 do { for(i=0;i<N;i++)if(!v[i]&&d[i]<t) t=d[i],p=i; // 找未标记中的最小值 for(v[p]=1,i=0;i<N;i++)if(!v[i])if(t=d[p]+a[p][i],t<d[i]) d[i]=t; // 更新dist }while(t=Inf, p!=v2); return d[p]; } int main() { int arcs[MAXN][MAXN],N; GetData(arcs,N); cout << Dijkstra(arcs,N,0,N-1) << endl; return 0; }