admin管理员组文章数量:1577818
//原本两个测试点错误,但是优化时只是改了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;
}
版权声明:本文标题:PAT A1003 Emergency 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1727824058a1132060.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论