枚举每头牛到所有牧场的距离,加到res
数组中
res[i]
表示所有牛到第i
个牧场的距离和,最后求最小的res[i]
就好了
循环牛的次数最短路算法就ok
了,比枚举牧场快
堆优化dijkstra
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 810, M = 3000, INF = 0x3f3f3f3f;
int n, p, m;
int h[N], e[M], ne[M], w[M], idx;
bool st[N];
int id[N], dist[N], res[N];
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
void dijkstra(int start)
{
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
priority_queue<PII, vector<PII>, greater<PII>> heap;
dist[start] = 0;
heap.push({0, start});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
for (int i = 1; i <= p; i ++)
if (dist[i] == INF) res[i] = INF;
else res[i] += dist[i];
}
int main()
{
cin >> n >> p >> m;
for (int i = 0; i < n; i ++)
cin >> id[i];
memset(h, -1, sizeof h);
while (m --)
{
int x, y, z;
cin >> x >> y >> z;
add(x, y, z), add(y, x, z);
}
for (int i = 0; i < n; i ++)
dijkstra(id[i]);
int ans = INF;
for (int i = 1; i <= p; i ++)
ans = min(ans, res[i]);
cout << ans << '\n';
return 0;
}
spfa
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 810, M = 3000, INF = 0x3f3f3f3f;
int n, p, m;
int id[N];
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N], res[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void spfa(int start)
{
memset(dist, 0x3f, sizeof dist);
dist[start] = 0;
int hh = 0, tt = 1;
q[0] = start, st[start] = true;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
for (int i = 1; i <= p; i ++)
if (dist[i] == INF) res[i] = INF;
else res[i] += dist[i];
}
int main()
{
cin >> n >> p >> m;
for (int i = 0; i < n; i ++ ) cin >> id[i];
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
for (int i = 0; i < n; i ++ )
spfa(id[i]);
int ans = INF;
for (int i = 1; i <= p; i ++)
ans = min(ans, res[i]);
cout << ans << endl;
return 0;
}
大佬为啥 spfa 不用 memset(st, 0, sizeof st); 啊啊啊
spfa 结束时队列为空
QAQ 大佬为什么不可以在main函数 用奶牛来枚举
for(int i=1;i<=n;i++)
{
int j=id[i];
ans=min(ans,spfa[j])
}
为什么不可以这样
要求的是所有牛到一个牧场的最短路程和,你每次枚举奶牛的话,
spfa
第i
头牛时,得到的答案是这头牛到所有牧场的最短路,加上i
之前,也就是第i
头牛及以前的牛到所有牧场的距离,我们要求的是前n
头牛的啊大佬, for循环上是奶牛,但是 int j=id[i],这不就表示第i头奶牛在哪一个牧场吗,然后再枚举这个牧场,为什么这样不行啊 QAQ
结果不一定是有牛存在的牧场,是空的牧场就错了
大佬,我就是这样想的啊,for循环是循环奶牛,j是这个奶牛所在的牧场,反而用牧场来枚举的话会有空牧场,比如这个样例,1号就是空牧场,但是还是枚举了
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
可是你spfa求的是什么啊,这头牛所在牧场到所有牧场的距离和?这也不是答案啊,怎么和ans比较
还是到所有有牛的牧场的距离和?这样的话如果答案是所有牛到一一个空的牧场的距离和最短,就没搜索到答案
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
const int N=10000;
struct edge{
int v,w;
};
vector[HTML_REMOVED]e[N];
typedef pair[HTML_REMOVED]PII;
int d[N],n,m,id[N],s;
bool st[N];
int dj(int x){
memset(d,0x3f,sizeof d);
memset(st,0,sizeof st);
priority_queue[HTML_REMOVED]q;
d[x]=0,q.push({0,x});
while(q.size()){
auto t=q.top();
q.pop();
int u=t.second;
if(st[u]) continue;
st[u]=true;
for(auto ed:e[u]){
int v=ed.v,w=ed.w;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
q.push({-d[v],v});
}
}
}
int ans=0;
for(int i=1;i<=n;i){
int j=id[i];
if(d[j]==0x3f3f3f3f) return 0x3f3f3f3f;
else ans+=d[j];
}
return ans;
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=n;i) cin>>id[i];
for(int i=0;i[HTML_REMOVED]>a>>b>>c;
e[a].push_back({b,c});
e[b].push_back({a,c});
}
int res=0x3f3f3f3f;
for(int i=1;i<=n;i++){
int j=id[i];
res=min(res,dj(j));
}
cout<<res;
return 0;
}
大佬,你看看我的代码,不知道自己怎么错了QAQ
你这做法就是上一条回答中我说的第二种,dijkstra中求的是当前枚举的牛所在的牧场到所有有牛的牧场的距离和,你预设了答案的那个草牧场一定不是空牧场,这是错的
反例,答案是4,空牧场
···
3 5 4
1
2
3
1 4
2 4
4 5
5 3
···
谢谢大佬’‘QAQ