求最短路径 ：
//如果需要加点权，第二边权，（最短路径不唯一的情况）求最短路径个数
//最短路径与最短距离，
//最短距离条件下获取的物资最多，或者花费最少
//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];
}
}
}
}
}
