#11求调
查看原帖
#11求调
781159
Lovely_Elaina楼主2023/1/6 21:28

刚学优先队列最短路,逛完知道什么错但是不知道怎么改,万分感谢

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 510;
const int P = 810;
const int C = 1460;

priority_queue<PII,vector<PII>, greater<PII> > q;

struct node{
    int to,len,next;
}a[C*2];

int n,p,c,k; bool f[P];
int d[P],pre[P],w[N];

void add(int u,int v,int len){
	a[++k] = {v,len,pre[u]};
	pre[u] = k;
}

int bfs(int s){
    memset(f,0,sizeof(f));
    memset(d,0x3f,sizeof(d));
    d[s] = 0; q.push({0,s});
    
    while(!q.empty()){
		PII h = q.top(); q.pop();
		int dis = h.first,p = h.second; 
		
		if(f[p]) continue;
		f[p] = true;
		
		for(int i = pre[p];i;i = a[i].next){
			int to = a[i].to;
			if(dis + a[i].len < d[to]){
				d[to] = dis + a[i].len;
				q.push({d[to],to});
			} 
		} 
	}
    
    int sum = 0;
    for(int i = 1; i <= n; i++)
        sum += d[w[i]];
    return sum;
}

int main(){
    scanf("%d %d %d",&n,&p,&c);
    for(int i = 1; i <= n; i++)
        scanf("%d",&w[i]);
        
    
    int x,y,len;
    for(int i = 1; i <= c; i++){
        scanf("%d %d %d",&x,&y,&len);
        add(x,y,len);
        add(y,x,len);
    }
    
    int ans = 0x3f3f3f3f;
    for(int i = 1; i <= p; i++)
        ans = min(ans,bfs(i));
    printf("%d\n",ans);
    return 0;
}
2023/1/6 21:28
加载中...