A1003 Emergency

这题只要用到Dijkstra的模版即可
开辟数组w[maxn]记录到该点的最大权值
开辟数组num[maxn]记录到该点的最短路径条数（注意不要放错位置）

            if(G[u][v]!=INF&&vis[v]==false){if(d[u]+G[u][v]<d[v]){d[v]=d[u]+G[u][v];w[v]=w[u]+weight[v];num[v]=num[u];}else if(d[u]+G[u][v]==d[v]){if(w[u]+weight[v]>w[v]){w[v]=w[u]+weight[v];}num[v]=num[v]+num[u];}}

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
const int INF=100000;
int n,m,c1,c2;int G[maxn][maxn];
int vis[maxn]={false};
int w[maxn];
int weight[maxn];
int num[maxn];//表示起点s到达顶点u的最短路径条数
int d[maxn];void Dijkstra(int s)
{fill(d,d+maxn,INF);fill(w,w+maxn,0);fill(num,num+maxn,0);d[s]=0;num[s]=1;w[s]=weight[s];for(int i=0;i<n;i++){int u=-1,min=INF;for(int j=0;j<n;j++){if(d[j]<min&&vis[j]==false){u=j;min=d[j];}}if(u==-1) return;vis[u]=true;for(int v=0;v<n;v++){if(G[u][v]!=INF&&vis[v]==false){if(d[u]+G[u][v]<d[v]){d[v]=d[u]+G[u][v];w[v]=w[u]+weight[v];num[v]=num[u];}else if(d[u]+G[u][v]==d[v]){if(w[u]+weight[v]>w[v]){w[v]=w[u]+weight[v];}num[v]=num[v]+num[u];}}}}}
int main()
{fill(G[0],G[0]+maxn*maxn,INF);scanf("%d%d%d%d",&n,&m,&c1,&c2);for(int i=0;i<n;i++){scanf("%d",&weight[i]);}for(int i=0;i<m;i++){int t1,t2;scanf("%d%d",&t1,&t2);scanf("%d",&G[t1][t2]);G[t2][t1]=G[t1][t2];}Dijkstra(c1);printf("%d %d",num[c2],w[c2]);}

A1018 Public Bike Management

这题的“第二标尺”相比上一题而言复杂了许多，因此使用的是Dijkstra+DFS的做法

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
const int INF=100000;int G[maxn][maxn];
int d[maxn];
bool vis[maxn]={false};
int Cmax,N,Sp,M;
int weight[maxn];vector<int> pre[maxn];
int minNeed=INF,minRemain=INF;
vector<int> tempPath,path;
void Dijkstra(int 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){if(d[v]>d[u]+G[u][v]){d[v]=d[u]+G[u][v];pre[v].clear();pre[v].push_back(u);}else if(d[v]==d[u]+G[u][v]){pre[v].push_back(u);                   }}}}
}void DFS(int v)
{if(v==0) //如果递归到起点{tempPath.push_back(v);int need=0,remain=0; //计算这条路径的need和remainfor(int i=tempPath.size()-1;i>=0;i--){int id=tempPath[i];if(weight[id]>0){remain+=weight[id];}else{if(remain>=abs(weight[id])){remain-=abs(weight[id]);}else{need+=abs(weight[id])-remain;remain=0;}}}if(need<minNeed) //如果发现这条路径的need或者remain更优，那么更新路径 path=tempPath{minNeed=need;minRemain=remain;path=tempPath;}else if(need==minNeed&&remain<minRemain){minRemain=remain;path=tempPath;}tempPath.pop_back(); //起点处理完毕，pop，returnreturn;}tempPath.push_back(v); //对pre进行深搜for(int i=0;i<pre[v].size();i++){DFS(pre[v][i]);}tempPath.pop_back();}int main()
{fill(G[0],G[0]+maxn*maxn,INF);scanf("%d%d%d%d",&Cmax,&N,&Sp,&M);for(int i=1;i<=N;i++){scanf("%d",&weight[i]);weight[i]=weight[i]-Cmax/2;}for(int i=0;i<M;i++){int t1,t2;scanf("%d%d",&t1,&t2);scanf("%d",&G[t1][t2]);G[t2][t1]=G[t1][t2];}Dijkstra(0);DFS(Sp);printf("%d ",minNeed);for(int i=path.size()-1;i>=0;i--){printf("%d",path[i]);if(i>0) printf("->");}printf(" %d",minRemain);return 0;
}

A1087 All Roads Lead to Rome

Dijkstra+DFS的终极模版，同时熟练了map的使用

#include<bits/stdc++.h>
using namespace std;
const int maxn=400;
const int INF=10000000;
int n,k;
string start;//起点城市
map<string,int> city2index;
map<int,string> index2city;
int numCity=1;
int weight[maxn];
int G[maxn][maxn];
int d[maxn];
int numPath=0;
int maxWeight=-INF;
double avgMaxWeight=-INF;
bool vis[maxn];
vector<int> pre[maxn];
vector<int> tempPath,path;void c2i(string city)
{city2index[city]=numCity;index2city[numCity]=city;numCity++;
}void Dijkstra(int s)
{fill(vis,vis+maxn,false);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){if(d[v]>d[u]+G[u][v]){d[v]=d[u]+G[u][v];pre[v].clear();pre[v].push_back(u);}else if(d[v]==d[u]+G[u][v]){pre[v].push_back(u);}}}}}void DFS(int v)
{if(v==0){tempPath.push_back(v);numPath++;int lengthPath=0; //记录路上有几个城市int tempWeight=0;double avgWeight=0;for(int i=tempPath.size()-2;i>=0;i--){int id=tempPath[i];tempWeight+=weight[id];}lengthPath=tempPath.size()-1;avgWeight=1.0*tempWeight/lengthPath;if(tempWeight>maxWeight){maxWeight=tempWeight;avgMaxWeight=avgWeight;path=tempPath;}else if(tempWeight==maxWeight){if(avgWeight>avgMaxWeight){avgMaxWeight=avgWeight;path=tempPath;}}tempPath.pop_back();return;}tempPath.push_back(v);for(int i=0;i<pre[v].size();i++){DFS(pre[v][i]);}tempPath.pop_back();}int main()
{fill(G[0],G[0]+maxn*maxn,INF);scanf("%d%d",&n,&k);cin>>start;city2index[start]=0;index2city[0]=start;for(int i=1;i<=n-1;i++){string city;int w;cin>>city>>w;c2i(city);weight[city2index[city]]=w;}for(int i=0;i<k;i++){string c1,c2;cin>>c1>>c2;scanf("%d",&G[city2index[c1]][city2index[c2]]);G[city2index[c2]][city2index[c1]]=G[city2index[c1]][city2index[c2]];}Dijkstra(0);int ed=city2index["ROM"];DFS(ed);printf("%d %d %d %.0f\n",numPath,d[ed],maxWeight,avgMaxWeight);for(int i=path.size()-1;i>=0;i--){cout<<index2city[path[i]];if(i!=0) printf("->");}return 0;}