3.香甜的黄油

1127. 香甜的黄油 - AcWing题库

枚举就行，枚举奶油放在哪个点上，每个点都去跑一遍最短路，然后去看奶油放在哪个点上牛牛到奶油的距离之和最小

Code：

#include 
using namespace std;
const int mxn=2e3+10,mxe=2e3+10,mnf=0x3f3f3f3f;
struct ty{int to,next,w;
}edge[mxe<<1];
struct ty2{int x,dis;bool operator< (const ty2 &a) const{return a.dis mp;
priority_queue q;
int N,n,m,x,y,w,tot=0;
int head[mxn],dis[mxn],vis[mxn];
void add(int u,int v,int w){edge[tot].w=w;edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;
}
void init(){tot=0;mp.clear();for(int i=0;i<=n;i++){head[i]=-1;dis[i]=mnf;vis[i]=0;}while(!q.empty()) q.pop();
}
void init2(){for(int i=0;i<=n;i++){vis[i]=0;dis[i]=mnf;}while(!q.empty()) q.pop();
}
int dij(int s){init2();dis[s]=0;ty2 u;u.dis=dis[s],u.x=s;q.push(u);while(!q.empty()){ty2 u=q.top();q.pop();if(vis[u.x]) continue;vis[u.x]=1;for(int i=head[u.x];~i;i=edge[i].next){if(vis[edge[i].to]) continue;if(dis[edge[i].to]>dis[u.x]+edge[i].w){dis[edge[i].to]=dis[u.x]+edge[i].w;ty2 tmp;tmp.dis=dis[edge[i].to];tmp.x=edge[i].to;q.push(tmp);}}}int res=0;for(int i=1;i<=n;i++){if(mp[i]){if(dis[i]==mnf) return mnf;res+=dis[i]*mp[i];}}return res;
}
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>N>>n>>m;init();for(int i=1;i<=N;i++) cin>>x,mp[x]++;for(int i=1;i<=m;i++){cin>>x>>y>>w;add(x,y,w);add(y,x,w);}int ans=mnf;for(int i=1;i<=n;i++){ans=min(ans,dij(i));}cout<

#include 
using namespace std;
const int mxn=2e3+10,mxe=1e5+10,mnf=0x3f3f3f3f;
struct ty{int to,next;double w;
}edge[mxe<<1];
queue q;
int n,m,x,y,w,tot=0,s,t;
int head[mxn],vis[mxn];
double dis[mxn];
void add(int u,int v,double w){edge[tot].w=w;edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;
}
void init(){tot=0;for(int i=0;i<=n;i++){head[i]=-1;vis[i]=0;}while(!q.empty()) q.pop();
}
double spfa(int u,int v){dis[u]=1;q.push(u);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];~i;i=edge[i].next){if(dis[edge[i].to]

#include 
using namespace std;
const int mxn=5e2+10,mxe=5e2+10,mnf=0x3f3f3f3f;
struct ty{int to,next,w;
}edge[mxe<<1];
queue q;
string s;
int m,n,len=0,p,tot=0;
int a[mxn],head[mxn],dis[mxn],vis[mxn];
void add(int u,int v,int w){edge[tot].w=w;edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;
}
void init(){tot=0;len=0;s.clear();for(int i=0;i<=n;i++){head[i]=-1;dis[i]=mnf;}while(!q.empty()) q.pop();
}
void spfa(){dis[1]=0;vis[1]=1;q.push(1);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];~i;i=edge[i].next){if(dis[edge[i].to]>dis[u]+edge[i].w){dis[edge[i].to]=dis[u]+edge[i].w;if(!vis[edge[i].to]){vis[edge[i].to]=1;q.push(edge[i].to);}}}}
}
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>m>>n;init();getline(cin,s);for(int i=1;i<=m;i++){len=0;getline(cin,s);stringstream ssin(s);while(ssin>>p) a[++len]=p; for(int i=1;i<=len;i++){for(int j=i+1;j<=len;j++){add(a[i],a[j],1);add(a[j],a[i],1);}}}spfa();if(dis[n]==mnf) cout<<"NO"<<'\n';else cout<