求最短路径 ：
//如果需要加点权，第二边权，（最短路径不唯一的情况）求最短路径个数
//最短路径与最短距离，
//最短距离条件下获取的物资最多，或者花费最少//1 最短路径
//只需要Dijkstra算法初始化的时候，让每个结点的前驱节点初始化为其本身，
//随着程序的运行，只要是和源点联通的结点，其前驱节点一定会发声变化
//而且只有在d[]发声变化时，其前驱节点的值才会发声变化，源点除外
int pre[maxn];void Dijk(int s){for(int i=0;i<n;i++) pre[i]=i;//pre[s]=s;fill(d,d+maxn,inf);d[s]=0;for(int i=0;i<n;i++){int u=-1,min=inf;for(int j=0;j<n;j++){if(vis[j]==false&&d[j]<min){min=d[j];u=j;}}if(u==-1) return ;vis[u]=true;for(int v=0;v<n;v++){if(vis[v]==false&&G[u][v]!=inf&&d[v]>G[u][v]+d[u]){d[v]=G[u][v]+d[u]; pre[v]=u; // }} }
}
void dfs(int s,int v){if(s==v){printf("%d\n",s);return ;}dfs(s,pre[v]);//即是递归 就是递推 printf("%d\n",v);
}
Dijkstra的三种基本包装情况：
//最小距离相等的情况下，花费最少
int Cost[maxn][maxn];//
int c[maxn];//s到各个点的最少花费 void Dijk(int s){fill(d,d+maxn,inf);d[s]=0;c[s]=0; for(int i=0;i<n;i++){int u=-1,min=inf;for(int j=0;j<n;j++){if(vis[j]==false&&d[j]<min){min=d[j];u=j;}}if(u==-1) return ;vis[u]=true;for(int v=0;v<n;v++){if(vis[v]==false&&G[u][v]!=inf){if(d[v]>G[u][v]+d[u]){d[v]=G[u][v]+d[u];c[v]=c[u]+Cost[u][v];}else if(d[v]==G[u][v]+d[u]&&c[u]+Cost[u][v]<c[v]){c[v]=c[u]+Cost[u][v];}}} }
}
//获取每个点的最大物资
int weight[maxn];
int w[maxn];void Dijk(int s){fill(d,d+maxn,inf);memset(w,0,sizeof(w));d[s]=0;w[s]=weight[s];for(int i=0;i<n;i++){int u=-1,min=inf;for(int j=0;j<n;j++){if(vis[j]==false&&d[j]<min){min=d[j];u=j;}}if(u==-1) return ;vis[u]=true;for(int v=0;v<n;v++){if(vis[v]==false&&G[u][v]!=inf){if(G[u][v]+d[u]<d[v]){d[v]=G[u][v]+d[u];w[v]=w[u]+weight[v];}else if(G[u][v]+d[u]==d[v]&&w[u]+weight[v]<w[v]){w[v]=w[u]+weight[v];} }} }
}
//最短路径个数
int num[maxn];
memset(num,0,sizeof(num));void Dijk(int s){fill(d,d+maxn,inf);d[s]=0;num[s]=1;for(int i=0;i<n;i++){int u=-1,min=inf;for(int j=0;j<n;j++){if(vis[j]==false&&d[j]<min){min=d[j];u=j;}}if(u==-1) return ;vis[u]=true;for(int v=0;v<n;v++){if(vis[v]==false&&G[u][v]!=inf){if(d[v]>G[u][v]+d[u]){d[v]=G[u][v]+d[u]; num[v]=num[u]; }else if(d[v]==G[u][v]+d[u]){num[v]+=num[u];} }} }
}