admin管理员组

文章数量:1577823

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

版权声明：本文标题：PAT——Emergency（测试点2无法通过的同学快进来看看） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1727823642a1132017.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。