PAT 1003 Emergency

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了PAT 1003 Emergency，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1582字，纯文字阅读大概需要3分钟。

内容图文

题目大意：给定城市数、道路数以及每个城市中救援人员的数量，求从起点到终点的最短路径条数以及这些路径中救援人员之和的最大值。

思路：最短路径问题，可用dijkstra解决，在其基础之上记录最短路径数以及所有路径中权重之和的最大值。

 

一共交了4次才过，被卡在了测试点1和2。

参考网上的博客，发现问题出在两种特殊情况上：

//相同路径长度，更新时不是+1而是+num[u]
4 5 0 3
1 4 1 2
0 1 1
0 2 2
0 3 4
1 2 1
2 3 2
//输出 3 8

 

//只有一个城市的情况
1 0 0 0
2
//输出 1 2

 

个人代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f;
int mp[505][505];
int dis[505];
int num[505];
int w[505];
int vis[505];
int weight[505];
int n,m;

void dijkstra(int c1,int c2)
{
    int u;
    memset(vis,0,sizeof(vis));
    memset(num,0,sizeof(num));
    memset(weight,0,sizeof(weight));
    for(int i=0;i<n;i++)
    {
        dis[i]=mp[c1][i];
        weight[i]=w[i]+w[c1];
        if(dis[i]!=inf) num[i]+=1;
    }    
    vis[c1]=1;
    dis[c1]=0;
    weight[c1]=w[c1];
    for(int i=0;i<n;i++)
    {
        int minn=inf;
        for(int j=0;j<n;j++)
        {
            if(dis[j]<minn&&!vis[j])
            {
                u=j;
                minn=dis[j];
            }
        }
        if(minn==inf) break;
        vis[u]=1;
        for(int j=0;j<n;j++)
        {
            if(!vis[j]&&dis[j]>=dis[u]+mp[u][j])
            {
                if(dis[j]==dis[u]+mp[u][j])
                {
                    num[j]+=num[u];
                    weight[j]=max(weight[j],w[j]+weight[u]);
                    continue;
                }
                dis[j]=dis[u]+mp[u][j];
                num[j]=num[u];
                weight[j]=w[j]+weight[u];
            }
        }
    }
}

int main()
{
    fill(dis,dis+505,inf);
    fill(w,w+505,0);
    int c1,c2;
    scanf("%d%d%d%d",&n,&m,&c1,&c2);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i==j) mp[i][j]=0;
            else mp[i][j]=inf;
        }
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&w[i]);
    }
    for(int i=0;i<m;i++)
    {
        int a,b,l;
        scanf("%d%d%d",&a,&b,&l);
        mp[a][b]=mp[b][a]=min(l,mp[a][b]);
    }
    dijkstra(c1,c2);
    printf("%d %d\n",num[c2],weight[c2]);
    return 0;
}

 

内容总结

以上是互联网集市为您收集整理的PAT 1003 Emergency全部内容，希望文章能够帮你解决PAT 1003 Emergency所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---