317号子任务

201903-5

为了过前60分，想使用dijikstra优化算法的，但是最后还是只过了35分。这里的思路只需要先将所有的行星据点进行一次dijikstra，分别存储所有点到行星的最短距离，最后使用一个优先队列存储所有的距离就可以了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int pro[10004];
int graph[10004][10004];
int n,m,k;
struct node{
    int dis;//表示起点到终点的距离
    int id;//表示终点的序号
    node(){}
    node(int a,int b):dis(a),id(b){}
    bool operator<(const node& t)const{
        return dis>t.dis;
    }
};
struct edge{
    int to;
    int cost;
    edge(){}
    edge(int a,int b):to(a),cost(b){}
};
vector<edge>G[10004];
priority_queue<int,vector<int>,greater<int> >dis[10004];
void dijikstra(int s){
    priority_queue<node>que;//最短路小的优先级高
    int d[10004];
    memset(d,INF,sizeof(d));
    d[s]=0;
    que.push(node(0,s));
    while(!que.empty()){
        node no=que.top();
        que.pop();
        int v=no.id;
        if(d[v]<no.dis){
            continue;
        }
        dis[v].push(no.dis);
        for(int i=0;i<G[v].size();i++){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(node(d[e.to],e.to));
            }
        }
    }
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>pro[i];
    }
    int x,y,z;
    memset(graph,INF,sizeof(graph));
    for(int i=0;i<m;i++){
        cin>>x>>y>>z;
        graph[x][y]=graph[y][x]=min(graph[x][y],z);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j&&graph[i][j]!=INF)
                G[i].push_back(edge(j,graph[i][j]));
        }
    }
    for(int i=1;i<=n;i++){
        if(pro[i]==1){
            dijikstra(i);
        }
    }
    for(int i=1;i<=n;i++){
        int sum=0;
        int cnt=k;
        while(!dis[i].empty()&&cnt>0){
            cnt--;
            sum+=dis[i].top();
            dis[i].pop();
        }
        cout<<sum<<endl;
    }
    //system("pause");
    return 0;
}