wa 6,7求助
查看原帖
wa 6,7求助
292029
幽理家的男人楼主2020/10/30 08:13
 #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1010;
const int inf=2333333333333;
typedef struct b{
	int pos,dis,c;
    bool operator < (const b& o) const{
	    return (dis>o.dis)||(dis==o.dis&&c>o.c);//根据花费和经过的城市数排序
	}
}node;
int g1[maxn][maxn],g2[maxn][maxn];//g1是花费,g2是i到j经过的城市数
int dis[maxn],c[maxn],go[maxn],a,b,n,vis[maxn],tot;
priority_queue<node> que;
signed main(){
	cin>>a>>b>>n;
    for(int i=0;i<maxn;++i){
    	for(int j=0;j<maxn;++j){
    		g1[i][j]=g2[i][j]=inf;
		}
	}
	int cost,temp,num;
	for(int i=1;i<=n;++i){
		cin>>cost>>num;
		for(int j=1;j<=num;++j){
		    cin>>go[j];
		    tot=max(tot,go[j]);//记录城市数目
		}
		for(int j=1;j<=num;++j){
			for(int k=j+1;k<=num;++k){
				if((cost<g1[go[j]][go[k]])){//建图
					g1[go[j]][go[k]]=cost;
					g2[go[j]][go[k]]=k-j;
				}
				else if(cost==g1[go[j]][go[k]]&&g2[go[j]][go[k]]>k-j){
					g2[go[j]][go[k]]=k-j;
				}
			}
		}
	}
	for(int i=1;i<=tot;++i){
		dis[i]=inf;
		c[i]=inf;
	}
	dis[a]=0;
	c[a]=0;
	que.push((node){a,0,0});
	while(!que.empty()){//dij
		node temp=que.top();
		que.pop();
		int u=temp.pos;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=1;i<=tot;++i){
            if(g1[u][i]==inf) continue;
            if(g1[u][i]+dis[u]<dis[i]){
            	dis[i]=g1[u][i]+dis[u];
            	c[i]=g2[u][i]+c[u];
            	que.push((node){i,dis[i],c[i]});
			}
			if(g1[u][i]+dis[u]==dis[i]&&c[i]>c[u]+g2[u][i]){
				c[i]=c[u]+g2[u][i];
				que.push((node){i,dis[i],c[i]});
			}
		}
	}
	if(c[b]==inf) cout<<-1; 
	else cout<<dis[b]<<' '<<c[b];
} 

wa了第6个点和第7个点(蒟蒻找不到原因),下面是第六个点的数据。

219 800 4

934996703 15

988 698 539 71 990 334 225 888 592 385 656 479 98 736 160

432052274 41

333 625 340 95 840 344 129 110 315 347 909 670 402 616 9 451 154 79 440 839 656 328 431 392 983 261 841 70 772 114 105 90 323 551 929 666 32 390 730 651 2

203909483 88

11 285 771 441 725 609 448 404 391 839 738 3 679 808 775 144 790 879 234 464 781 514 482 164 904 814 894 554 815 728 171 177 13 293 970 89 901 417 844 644 608 581 646 638 740 420 782 882 650 367 345 431 880 826 946 783 991 191 688 158 919 210 334 283 502 655 371 755 72 214 398 146 395 316 238 449 119 246 695 993 544 829 983 734 869 140 652 78

925557826 87

932 832 656 686 903 221 435 933 719 829 601 956 995 49 74 811 864 240 408 910 232 951 738 567 685 958 58 688 388 883 974 319 67 981 356 969 554 142 254 272 970 854 227 317 652 127 469 891 534 378 123 485 468 689 521 425 746 208 812 533 130 47 514 837 367 978 620 338 300 825 916 616 431 742 899 457 275 277 931 111 744 619 631 168 717 191 980

2020/10/30 08:13
加载中...