admin管理员组

文章数量:1577825

//原本两个测试点错误,但是优化时只是改了num和c的赋值顺序竟然全部ac了
//c[s]=weight[s]; 
//fill(G[0],G[0]+MAXN*MAXN,INF);必须写G[0],写G就不对 
//PAT A1003
#include<cstdio>
#include<cstring>
#include<algorithm>
//#define LOCAL
using namespace std;

const int MAXN=510;
const int INF=1000000000;
bool vis[MAXN]={false};
int n,m,S,T;//到T的最短路径就是d[T]啊 
int c[MAXN],num[MAXN],d[MAXN];//表示每个顶点的救援队 
int G[MAXN][MAXN],weight[MAXN];
//从整个函数讲,每个点都会被优化到,只要从起点到这个点可达的话。
//因为所有点一开始都是INF,只要相连,就一定会被至少优化一次 
void dijkstra(int s){
	fill(d,d+MAXN,INF);//设置起点到所有点的最大 
	memset(num,0,sizeof(num));
	memset(c,0,sizeof(c)); 
	d[s]=0;
	c[s]=weight[s];
	num[s]=1;//初始化,很重要! 
	for(int i=0;i<n;i++){//循环N次,每次找到一个距离最短的未被访问的点
		int u=-1,MIN=INF;
		for(int j=0;j<n;j++){
			if(vis[j]==false&&d[j]<MIN){
				u=j;
				MIN=d[j];
			}
		}
		if(u==-1) return;//没找到 
		vis[u]=true;
		//找到和u直接相连,未被访问且可达.优化。 
		for(int v=0;v<n;v++){
			if(vis[v]==false&&G[u][v]!=INF){
				if(d[u]+G[u][v]<d[v]){
					d[v]=d[u]+G[u][v];
					c[v]=c[u]+weight[v];
					num[v]=num[u];
				}
				else if(d[u]+G[u][v]==d[v]){
					if(c[u]+weight[v]>c[v]){
						c[v]=c[u]+weight[v];
					}
					num[v]+=num[u];
				}  
				//如果距离大于它的话就不是最短路啊,就不要计数啊,因为第一条件就是最短路啊 
			}
		}
	}
}

int main(){
	#ifdef LOCAL
	freopen("A1003data.in","r",stdin);
	freopen("A1003data.out","w",stdout); 
	#endif 
	scanf("%d%d%d%d",&n,&m,&S,&T);
	for(int i=0;i<n;i++)
		scanf("%d",&weight[i]);
	fill(G[0],G[0]+MAXN*MAXN,INF);
	int h,l,z;
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&h,&l,&z);
		G[h][l]=z;
		G[l][h]=z;
	}
	dijkstra(S);
	printf("%d %d\n",num[T],c[T]); 
	return 0;
}

本文标签: PATEmergency