[CQOI2005]新年好

本文主要是介绍[CQOI2005]新年好，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

1.问题分析

数据被加强了就很烦，最后用堆优化dijkstra才能过。
最短路+爆搜。需要注意的细节还是比较多的。

2.具体代码

#include <bits/stdc++.h>using namespace std;const int N = 50010,M = 2e5+10,INF = 0x3f3f3f3f;typedef pair<int ,int > PII;
#define x first
#define y secondint n,m;
int s[6];
int h[N],e[M],ne[M],w[M],idx;
int d[6][N];
bool st[N];
void add(int a,int b,int v)
{e[idx]=b;w[idx]=v;ne[idx]=h[a];h[a]=idx++;
}void dijkstra(int start,int d[])
{priority_queue<PII,vector<PII>,greater<PII> > heap;memset(d,0x3f,N * 4);d[start]=0;memset(st,false,sizeof st);heap.push({0,start});while(heap.size()){auto t = heap.top();heap.pop();if(st[t.y]) continue;st[t.y]=1;for (int i = h[t.y]; ~i; i = ne[i]){int j = e[i];if (d[j] > d[t.y] + w[i]){d[j] = d[t.y] + w[i];heap.push({d[j], j});}}}
}int dfs(int u,int start,int dis)
{if(u>5)    return dis;int res=INF;for(int i=1;i<=5;i++){if(!st[i]){st[i]=1;res=min(res,dfs(u+1,i,dis+d[start][s[i]]));st[i]=0;}}return res;
}
int main()
{cin>>n>>m;memset(h,-1,sizeof h);s[0]=1;for(int i=1;i<=5;i++)scanf("%d",&s[i]);while(m--){int a,b,v;scanf("%d%d%d",&a,&b,&v);add(a,b,v),add(b,a,v);}for(int i=0;i<=5;i++)dijkstra(s[i],d[i]);memset(st,0,sizeof st);cout<<dfs(1,0,0)<<endl;return 0;
}

3.总结

注意双向边，边的容量乘2.
“关于SPFA,它死了。”

这篇关于[CQOI2005]新年好的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---