博客

## L2-001紧急救援c++


我被这个题目折磨了好久，这道题目和数据结构中学习的dijkstra算法最大的不同在于它不能对起始的节点初始化，如果进行初始化之后，其中第一个找到的最小路径的救援队数量为0，路径条数为0，然后就会导致错误。这个需要特别注意，然后就是在路径长度相等的情况下权重越大越好即可，就在普通dijkstra算法的判断条件dis[i]>dis[t]+citymap[t][i]加上了一个dis[i]=dis[t]+citymap[t][i]，来更新路径的条数、权重和父结点

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
const int MAX=10000;
int N,M,S,D;//N个城市、M条道路、出发地S、目的地D
vector<vector<int>> citymap;//城市地图
vector<int> team;//各个城市救援队的数量
vector<int> dis;//记录最短路径的长度
vector<int> visit;//记录是否访问
vector<int> father;//记录父节点
vector<int> weight;//最大消防员的数量
vector<int> differ;//不同的路径
void findpath()
{
    int x=father[D];
    stack<int> st;
    while(x!=-1)
    {
        st.push(x);
        x=father[x];
    }
    int sum=team[D];
    while(!st.empty())
    {
       cout<<st.top()<<" ";
       st.pop();
    }
    cout<<D<<endl;
    return ;
}
void Dis(){
    dis.resize(N,MAX);
    weight.resize(N,0);
    differ.resize(N,0);
    visit.resize(N,false);
    father.resize(N,-1);
    differ[S]=1;
    weight[S]=team[S];
    dis[S]=0;
    for(int i=0;i<N;i++)
    {
        int temp=MAX,t=-1;
        for(int j=0;j<N;j++)
        {
            if(!visit[j]&&dis[j]<temp)
            {
                temp=dis[j];
                t=j;
            }
        }
        visit[t]=true;
        for(int j=0;j<N;j++)
        {
            if(!visit[j]&&dis[j]>dis[t]+citymap[t][j])
            {
                dis[j]=dis[t]+citymap[t][j];
                father[j]=t;
                weight[j]=weight[t]+team[j];
                differ[j]=differ[t];
            }
            else if(!visit[j]&&dis[j]==dis[t]+citymap[t][j]){
                differ[j]+=differ[t];
                if(weight[j]<(weight[t]+team[j]))
                {
                    weight[j]=weight[t]+team[j];
                    father[j]=t;
                }
            }
        }
    }
    return ;
}
int main()
{
    cin>>N>>M>>S>>D;
    citymap.resize(N,vector<int>(N,MAX));
    team.resize(N);
    for(int i=0;i<N;i++) cin>>team[i];
    for(int i=0;i<M;i++)
    {
        int x,y,cost;
        cin>>x>>y>>cost;
        citymap[x][y]=cost;
        citymap[y][x]=cost;
    }
    Dis();
    cout<<differ[D]<<" "<<weight[D]<<endl;
    findpath();
}