fill與memset的區別介紹

例一

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=500;
const int INF=1000000000;
bool isin[maxn]={false};
int G[maxn][maxn];
int path[maxn],rescue[maxn],num[maxn];
int weight[maxn];
int citynum,roadnum,begins,e;void Dijisktra(int a){fill(path,path+maxn,INF);//記錄最短距離memset(rescue,0,sizeof(rescue));//記錄點權memset(num,0,sizeof(num));//記錄最短路徑的條數path[a]=0;rescue[a]=weight[a];num[a]=1;for(int i=0;i<citynum;i++){int pi=-1,pv=INF;for(int j=0;j<citynum;j++){//找最短距離的結點if(isin[j]==false&&path[j]<pv){pi=j;pv=path[j];}}if(pi==-1) return;isin[pi]=true;for(int k=0;k<citynum;k++){if(isin[k]==false&&G[pi][k]!=INF){if(G[pi][k]+path[pi]<path[k]){path[k]=G[pi][k]+path[pi];num[k]=num[pi];//更新最短路徑數：不相同就覆蓋rescue[k]=rescue[pi]+weight[k];}else if(G[pi][k]+path[pi]==path[k]){if(rescue[pi]+weight[k]>rescue[k])rescue[k]=rescue[pi]+weight[k];//存大值num[k]+=num[pi];//最短路徑條數之和：相同累加}}}}
}
int main(){int v1,v2;//頂點及邊權-距離fill(G[0],G[0]+maxn*maxn,INF);cin>>citynum>>roadnum>>begins>>e;for(int i=0;i<citynum;i++){cin>>weight[i];//記錄點權-救援小組數目}for(int j=0;j<roadnum;j++){cin>>v1>>v2>>G[v1][v2];//建立無向圖G[v2][v1]=G[v1][v2];}Dijisktra(begins);cout<<num[e]<<" "<<rescue[e];return 0;
}

例二

#include <iostream>
using namespace std;
const int maxn=100;
const int INF=1000000000;
bool isin[maxn]={false};
int G[maxn][maxn],expense[maxn][maxn];
int path[maxn],cost[maxn],pre[maxn];
int citynum,roadnum,b,e;void Dijisktra(int a){//求最短路徑fill(path,path+maxn,INF);fill(cost,cost+maxn,INF);path[a]=0;cost[a]=0;for(int i=0;i<citynum;i++) pre[i]=i;for(int i=0;i<citynum;i++){int m=-1,mv=INF;for(int j=0;j<citynum;j++){if(isin[j]==false&&path[j]<mv){m=j;mv=path[j];}}if(m==-1) return;isin[m]=true;for(int k=0;k<citynum;k++){if(isin[k]==false&&G[m][k]!=INF){if(G[m][k]+path[m]<path[k]){path[k]=G[m][k]+path[m];cost[k]=expense[m][k]+cost[m];pre[k]=m;}else if(G[m][k]+path[m]==path[k]){if(cost[k]>expense[m][k]+cost[m])cost[k]=expense[m][k]+cost[m];pre[k]=m;}}}}
}
void DFSprint(int now){//打印if(now==b){cout<<now<<" ";return;}DFSprint(pre[now]);cout<<now<<" ";
}
int main(){int v1,v2;fill(G[0],G[0]+maxn*maxn,INF);fill(expense[0],expense[0]+maxn*maxn,INF);cin>>citynum>>roadnum>>b>>e;for(int i=0;i<roadnum;i++){cin>>v1>>v2>>G[v1][v2]>>expense[v1][v2];G[v2][v1]=G[v1][v2];expense[v2][v1]=expense[v1][v2];}Dijisktra(b);DFSprint(e);cout<<path[e]<<" "<<cost[e]<<endl;return 0;
}

拓展

用迪杰斯特拉+DFS求最短路徑的方法
關鍵代碼：

const int maxn=100;
const int INF=10000000000;
bool isin[maxn]={false};
int G[maxn][maxn],num;
int path[maxn],w[maxn];
vector<int> pre[maxn];//記錄最短路徑的前驅：考慮會有多個
vector<int> minPath,temPath;//只記錄最優或當前路徑void Dijisktra(int a){fill(path,path+maxn,INF);path[a]=0;for(int i=0;i<num;i++){int m=-1,mv=INF;for(int j=0;j<num;j++){if(isin[j]==false&&path[j]<mv){m=j;mv=path[j];}}if(m==-1) return;isin[m]=true;for(int k=0;k<num;k++){if(isin[k]==false&&G[m][k]!=INF){if(G[m][k]+path[m]<path[k]){path[k]=G[m][k]+path[m];//找到更優路徑，清空，裝最短的pre[k].clear();//m結點加入k結點的前驅列表中，即為pre[k][i]==m;pre[k].push_back(m);}else if(G[m][k]+path[m]==path[k]){
//此時有多條最短路徑，即存在多個前驅結點，直接加入即可pre[k].push_back(m);}}}}
}void DFSprint(int now,int begins){int optValue=0;if(now==begins){temPath.push_back(begins);if(value>optValue){//更新最優optValue=value;minPath=temPath;}temPath.pop_back();//彈出第一個return;}temPath.push_back(now);for(int i=0;i<pre[now].size();i++){//遍歷當前結點的前驅結點DFSprint(pre[now][i]);//不斷遞歸now結點的前驅列表}temPath.pop_back();//依次彈出第二個.....
}
//計算邊權和
int edge=0;
for(int i=temPath.size()-1;i>0;i--){int now=temPath[i],next=temPath[i-1];edge+=G[now][next];//計算邊權
}
//計算點權和
int weight=0;
for(int i=temPath.size()-1;i>0;i--){int now=temPath[i];//當前結點下標weight+=w[now];
}

例二：Dijiskatra+DFS

#include <iostream>
#include <vector>
using namespace std;
const int maxn=100;
const int INF=100000000;
bool isin[maxn]={false};
int G[maxn][maxn],expense[maxn][maxn];
int path[maxn],minValue=INF;
vector<int> pre[maxn],temPath,minPath;
int citynum,roadnum,b,e;void Dijisktra(int a){fill(path,path+maxn,INF);path[a]=0;for(int i=0;i<citynum;i++){int m=-1,mv=INF;for(int j=0;j<citynum;j++){if(isin[j]==false&&path[j]<mv){m=j;mv=path[j];}}if(m==-1) return;isin[m]=true;for(int k=0;k<citynum;k++){if(isin[k]==false&&G[m][k]!=INF){if(path[m]+G[m][k]<path[k]){path[k]=path[m]+G[m][k];pre[k].clear();pre[k].push_back(m);}else if(path[m]+G[m][k]==path[k]){pre[k].push_back(m);}}}}
}
void DFSprint(int now){int tempValue=0;if(now==b){temPath.push_back(now);for(int i=temPath.size()-1;i>0;i--){int v1=temPath[i],v2=temPath[i-1];tempValue+=expense[v1][v2];}if(tempValue<minValue){minValue=tempValue;minPath=temPath;}temPath.pop_back();//出隊}temPath.push_back(now);for(int i=0;i<pre[now].size();i++){DFSprint(pre[now][i]);}temPath.pop_back();
}
int main(){int v1,v2;fill(G[0],G[0]+maxn*maxn,INF);fill(expense[0],expense[0]+maxn*maxn,INF);cin>>citynum>>roadnum>>b>>e;for(int i=0;i<roadnum;i++){cin>>v1>>v2>>G[v1][v2]>>expense[v1][v2];G[v2][v1]=G[v1][v2];expense[v2][v1]=expense[v1][v2];}Dijisktra(b);DFSprint(e);for(int i=minPath.size()-1;i>=0;i--)cout<<minPath[i]<<" ";cout<<path[e]<<" "<<minValue<<endl;return 0;
}