动态规划，有向图，且 dp[i] 不能去到 dp[j] (i>=j)
参考程序
//动态规划 #include<iostream> using namespace std; int c[1001],f[1001],a[1001][1001]; int main() { int n,i,j,x; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) cin>>a[i][j]; for(i=1;i<=n;i++) f[i]=31415926; f[n]=0; for(i=n-1;i>=1;i--) for(x=i+1;x<=n;x++) if(a[i][x]>0 && f[x]!=31415926 && f[i]>f[x]+a[i][x]) //a[i][x] 表示从 i->x 的距离；f[i] 表示从 i->n 的最小值 { f[i]=f[x]+a[i][x]; c[i]=x;//记录下标 } cout<<"minlong="<<f[1]<<endl; j=c[1]; cout<<1<<" "<<c[1]<<" "; while(c[j]>0) { cout<<c[j]<<" "; j=c[j]; } return 0; }T5-1最短路径问题
Time Limit:1000MS Memory Limit:65536K Total Submit:47 Accepted:26
Description
例 5-1 最短路径问题 【问题描述】 平面上有N个点（N<=100),每个的坐标均在 -10000~10000 之间。其中的一些点之间有连线，则表示可从一个点到达另一个点，即两点之间有通路，通路的距离为两点之间的直线距离。现在的任务是找出从一个点到另一个点之间的最短路径。 输入 输入文件为 short.in，共 n+m+3 行，其中： 第一行为整数 N。 第二行到 N+1 行（共 N 行），每行两个整数 X 和 Y，描述了一个点的坐标（以一个空格分隔）。 第 N+2 行为一个整数M，表示图中连线的个数。 此后的 M 行，每行描述一条连线，由两个整数i 和 j 组成，表示第i 个点和第j个点之间有连线。 最后一行：两个整数 s 和 t ，分别表示源点和目标点。 输出： 输出文件为 short.out，仅一行，一个实数（保留两位小数），表示从 s 到 t 的最短路径长度。 【样例输入】 5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5 【样例输出】 3.41
算法一
Floyed-Warshall算法(o(n^3))不建议使用
适合处理有负边权的情况
w[u][v] 表示从 u->v 的最短距离
使用3层循环:
第一层 k 循环中间点
第二层 i 循环起点
第三层 j 循环终点
算法：
看是从 i->j 的路径近
还是先从 i->k 再从 k->j 的路径近
参考程序
#include<iostream> #include<cmath> #include<cstdio> #include<cmath> #include<iostream> #include<cstring> #include<cstdlib> using namespace std; double w[101][101]; int a[101][3]; int main() { int n, m, b, i, j, k, s, e, x, y; memset(w,127,sizeof(w)); scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&a[i][1],&a[i][2]);//第 i 个点的坐标 scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y);//第 x 与第 y 是联通的 w[x][y]=w[x][y]=sqrt(pow(double(a[x][1] - a[y][1]),2)+pow(double(a[x][2] - a[y][2]),2)); //算出两点的距离 } scanf("%d%d",&s,&e); // 要求算出 s->e 的最短路径 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if((i!=j) && (i!=k) && (j!=k) && (w[i][j]>w[i][k]+w[k][j])) w[i][j]=w[i][k]+w[k][j]; printf("%.2f",w[s][e]); return 0; }
算法二
Dijkstra算法 O(n^2)
用来计算一个点到其他所有点的最短路径的算法，是一种单源最短路径算法。只能计算起点只有一个的情况
Dijkstra算法不能处理负边权情况。
算法:
设起点为 s ，dis[v] 表示从 s->v 的最短路径
(a) 初始化 dis[v] = max; dis[s] = 0;(从s开始)
(b) for(i = 1; i <= n; i++)
1. 在没有被访问过的点中找一个顶点 u 使得 dis[u] 是最小的
2. u 标记为已确定最短路径
3. for 与 u 相连的每个未确定最短路径的顶点 v
if (dis[u] + w[u][v] < dis[v])
dis[v] = dis[u] + w[u][v];
(c) 算法结束：dis[v] 为 v 的前驱节点，用来输出路径
#include<iostream> #include<cmath> #include<cstdio> #include<cmath> #include<iostream> #include<cstring> #include<cstdlib> using namespace std; double w[101][101]; int a[101][3]; double maxx=1e30; double minl; double c[101]; bool b[101]; int main() { int n, m, i, j, k, s, e, x, y; memset(w,127,sizeof(w)); scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&a[i][1],&a[i][2]); for(i=1;i<=n;i++) for(j=1;j<=n;j++) w[i][j]=maxx; // w数组初始化最大 scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); w[x][y]=w[x][y]=sqrt(pow(double(a[x][1] - a[y][1]),2)+pow(double(a[x][2] - a[y][2]),2)); } scanf("%d%d",&s,&e); for(i=1;i<=n;i++) c[i]=w[s][i]; memset(b,false,sizeof(b));//Dijkstra最短路 b[s]=true;//从 s 开始查找 c[s]=0; for(i=1;i<=n-1;i++) { minl=maxx; k=0; for(j=1;j<=n;j++) // 查找新的路径 if((!b[j]) && (c[j]<minl)) { minl=c[j]; k=j; } if(k==0) break; // 若没有点更新，就退出 b[k]=true; for(j=1;j<=n;j++) if(c[k]+w[k][j]<c[j]) // 找最短路径 c[j]=c[k]+w[k][j]; } printf("%.2f",c[e]); return 0; }
