主流网站 技术,网站建设所需美工,福建企业网站建设,h5制作软件是什么意思正题
纪中题目链接:https://jzoj.net/senior/#main/show/3470 题目大意
在从起点经过k个标记点然后到终点的最短路。 解题思路
用SPFA求出起点和所有标记点的最短路#xff0c;然后暴力枚举标记点到达顺序。 时间负责度:O(K(NM)k!)O(K(NM)k!)O(K(NM)k!) code
#include…正题
纪中题目链接:https://jzoj.net/senior/#main/show/3470 题目大意
在从起点经过k个标记点然后到终点的最短路。 解题思路
用SPFA求出起点和所有标记点的最短路然后暴力枚举标记点到达顺序。 时间负责度:O(K(NM)k!)O(K(NM)k!)O(K(NM)k!) code
#includecstdio
#includequeue
#includecstring
#define ll long long
#define inf 1e181
#define N 50010
using namespace std;
struct line{long long to,next,w;
}a[N*2];
long long n,m,x,y,w,k,s,t,f[11][N],v[N],tot,ls[N],ans,mark[11],ok[11];
queueint q;
void addl()//加边
{scanf(%d%d%d,x,y,w);a[tot].toy;a[tot].ww;a[tot].nextls[x];ls[x]tot;
}
void spfa(long long x,long long num)//最短路
{q.push(x);v[x]1;f[num][x]0;while(!q.empty()){long long xq.front();q.pop();for(long long ils[x];i;ia[i].next){long long ya[i].to;if(f[num][x]a[i].wf[num][y]){f[num][y]f[num][x]a[i].w;if(!v[y]){v[y]true;q.push(y);}}}v[x]false;}
}
void dfs(long long dep,long long sum,long long be)
{if(depk) sumf[be][t];//到终点if(sumans) return;//剪枝if(depk){anssum;}for(long long i1;ik;i)if(!ok[i]){ok[i]1;dfs(dep1,sumf[be][mark[i]],i);ok[i]0;}
}
int main()
{scanf(%lld%lld%lld%lld%lld,n,m,k,s,t);for(long long i1;im;i)addl();for(int j0;jN;j) f[0][j]inf;spfa(s,0);for(long long i1;ik;i)//标号点求最短路{for(int j0;jN;j) f[i][j]inf;scanf(%lld,mark[i]);spfa(mark[i],i);}ansinf;dfs(0,0,0);//搜索if(ansinf) printf(-1);else printf(%lld,ans);
}
