首页 > 代码库 > 【最短路】【spfa】CDOJ1647 酌贪泉而觉爽， 处涸辙以犹欢。
【最短路】【spfa】CDOJ1647 酌贪泉而觉爽， 处涸辙以犹欢。
题意： 给你一个全为0的01串，问你能否通过一系列的变换，得到全为1的01串。 分析： 将每个01串看作一个点，每一个变换可以看作是一条有向边，现在问题可以转化 为找从“00..0”这个点到“11..1”这个点的最短路，那么可以使用spfa来解决这个问题。 对于每个CFT，建一条有向边，从si指向ti，权值为ti。然后跑spfa即可。
#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
queue<int>q;
int n,m,__next[100010],v[100010],e,first[(1<<20)+10],w[100010];
ll dis[(1<<20)+10];
bool inq[(1<<20)+10];
int trans(char T[]){
int len=strlen(T);
int res=0;
for(int i=0;i<len;++i){
res=res*2+T[i]-‘0‘;
}
return res;
}
void AddEdge(int U,int V,int W){
v[++e]=V;
w[e]=W;
__next[e]=first[U];
first[U]=e;
}
void spfa(int s)
{
memset(dis+1,0x7f,sizeof(dis));
q.push(s); inq[s]=1; dis[s]=0;
while(!q.empty())
{
int U=q.front();
for(int i=first[U];i;i=__next[i])
if(dis[v[i]]>dis[U]+(ll)w[i])
{
dis[v[i]]=dis[U]+(ll)w[i];
if(!inq[v[i]])
{
q.push(v[i]);
inq[v[i]]=1;
}
}
q.pop(); inq[U]=0;
}
}
int main(){
// freopen("k.in","r",stdin);
int x,y,z;
char s[30];
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%s",s);
x=trans(s);
scanf("%s%d",s,&z);
y=trans(s);
AddEdge(x,y,z);
}
spfa(0);
cout<<(dis[(1<<n)-1] < 100000000000001ll ? dis[(1<<n)-1] : -1)<<endl;
return 0;
}
【最短路】【spfa】CDOJ1647 酌贪泉而觉爽， 处涸辙以犹欢。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。