admin管理员组文章数量:1577830
Emergency
- 题目
- 答案
- 注意
题目
答案
#include<iostream>
#include<cstring>
using namespace std;
#define inf 0x3f3f3f3f
int map[501][501],dis[501],vis[501],cnt[501],init_num[501],max_num[501];
int n,m,start,last;
void init()
{
cin>>n>>m>>start>>last;
memset(map,inf,sizeof(map));
for(int i=0;i<n;i++)
{
map[i][i]=0;
cnt[i]=1;
}
for(int i=0;i<n;i++)
{
cin>>init_num[i];
max_num[i]=init_num[i];
}
for(int i=0;i<m;i++)
{
int x,y,z;
cin>>x>>y>>z;
map[x][y]=map[y][x]=z;
}
}
void dijkstra()
{
for(int i=0;i<n;i++)
dis[i]=map[start][i];
vis[start]=1;
int min,pos;
for(int t=0;t<n;t++)
{
min=inf,pos=-1;
for(int i=0;i<n;i++)
{
if(!vis[i]&&dis[i]<min)
{
min=dis[i];
pos=i;
}
}
if(pos==-1) break;
vis[pos]=-1;
for(int i=0;i<n;i++)
{
if(!vis[i]&&dis[pos]+map[pos][i]<dis[i])
{
dis[i]=dis[pos]+map[pos][i];
max_num[i]=max_num[pos]+init_num[i];
cnt[i]=cnt[pos];
}
else if(!vis[i]&&dis[pos]+map[pos][i]==dis[i])
{
cnt[i]+=cnt[pos];
if(max_num[pos]+init_num[i]>max_num[i])
{
max_num[i]=max_num[pos]+init_num[i];
}
}
}
}
}
int main()
{
init();
dijkstra();
if(start==last)
cout<<cnt[start]<<" "<<init_num[start];
else
cout<<cnt[last]<<" "<<init_num[start]+max_num[last];
}
注意
测试点2是起点与终点相同的情况,所以要分情况输出结果
该信息参考了这篇文章——PAT甲级1003 Emergency 测试点2一直不通过的原因
版权声明:本文标题:PAT——Emergency(测试点2无法通过的同学快进来看看) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1727823642a1132017.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论