原題鏈接CSP 201903-5 317號子任務

1.下面是30分的暴力代碼，僅僅使用常規的未優化的Dijkstra算法做的。

#include <bits/stdc++.h> using namespace std; #define ll long long const int MAX=10010; const int INF=1e8;int n,m,k; int f[MAX]; struct node {int v,w;node(int _v,int _w){v=_v;w=_w;} }; vector<int> x[MAX]; vector<node> g[MAX]; int d[MAX]; int vis[MAX]; void dijk(int s) {fill(d,d+MAX,INF);memset(vis,0,sizeof(vis));d[s]=0;for(int i=1;i<=n;i++){int u=-1;int MIN=INF;for(int j=1;j<=n;j++){if(vis[j]==0 && d[j]<MIN){u=j;MIN=d[j];}}if(u==-1)return ;vis[u]=1;for(int j=0;j<g[u].size();j++){int v=g[u][j].v;if(vis[v]==0 && d[u]+g[u][j].w<d[v]){d[v]=d[u]+g[u][j].w;}}} } int main() {std::ios::sync_with_stdio(false);cin>>n>>m>>k;for(int i=1;i<=n;i++){cin>>f[i];}while(m--){int u,v,w;cin>>u>>v>>w;g[u].push_back(node(v,w));g[v].push_back(node(u,w));}for(int i=1;i<=n;i++){dijk(i);ll sum=INF;for(int j=1;j<=n;j++){if(f[j]==1 && d[j]!=INF)x[i].push_back(d[j]);}sort(x[i].begin(),x[i].end());ll tmp=0;if(x[i].size()>=k){for(int j=0;j<k;j++){tmp+=x[i][j];}}else{for(int j=0;j<x[i].size();j++){tmp+=x[i][j];}}sum=min(sum,tmp);cout<<sum<<endl;}return 0; }

2.下面是100分的優化代碼，使用優化過的優先隊列+Dijkstra算法做的，有一點需要注意，做題的時候需要把握數據范圍的“魅力”，由上圖可知，對于60%的數據，保證行星發動機的數量與k相同，這點很重要，我開始僅僅只優化過了“優先隊列+Dijkstra算法”，后面對每一個點計算他與K個行星發動機的最短距離，交上去還是30分，于是我把后面的計算距離“由遍歷所有節點到行星發動機的距離改為遍歷行星發動機結點到每個結點的距離”，即for循環里的遍歷由1e4變為了1e2，極大的減少了計算過程，不過我這樣的想法本來是只想著通過60%的數據，沒想到100分了。

以下是滿分代碼

#include <bits/stdc++.h> using namespace std; const int N=1e4+10; const int INF=0x3f3f3f3f; #define ll long longint n,m,k; struct Node {int v;int w;Node(int _v,int _w){v=_v; w=_w;}friend bool operator < (const Node& a,const Node& b){return a.w>b.w;} }; int type[N]; vector<Node> adj[N]; vector<int> dis[N];ll d[N]; bool vis[N]; priority_queue<Node> q;void dijkstra(int s) {fill(d,d+N,INF);memset(vis,0,sizeof(vis));d[s]=0;q.push(Node(s,d[s]));while(!q.empty()){Node x=q.top();q.pop();int u=x.v;if(vis[u]==1) continue;vis[u]=1;for(int i=0;i<adj[u].size();i++){int v=adj[u][i].v;if(vis[v]==0 && d[u]+adj[u][i].w<d[v]){d[v]=d[u]+adj[u][i].w;q.push(Node(v,d[v]));}}} }int main() {std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m>>k;for(int i=1;i<=n;i++) cin>>type[i];for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;adj[u].push_back(Node(v,w));adj[v].push_back(Node(u,w));}for(int i=1;i<=n;i++){if(type[i]){dijkstra(i);for(int j=1;j<=n;j++){if(d[j]!=INF) dis[j].push_back(d[j]);}}}for(int i=1;i<=n;i++){sort(dis[i].begin(),dis[i].end());ll res=INF,tmp=0;if(dis[i].size()<=k){tmp=accumulate(dis[i].begin(),dis[i].end(),0);}else tmp=accumulate(dis[i].begin(),dis[i].begin()+k,0);cout<<min(res,tmp)<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的CSP 201903-5 317号子任务 暴力30分+优化100分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。