大意:不解释
思路:由于n极小,k也小,考虑状压后迭代乱搞.设状态dis[i][j]表示终点为i状态为j的最小路径长,将每个点的初始态扔进队列里迭代更新即可.
代码:
#include <iostream> #include <cstdio> #include <memory.h> #include <queue> #define r(x) x=read() #define MAXX 105 #define MAX(a,b) (a>b?a:b) #define MIN(a,b) (a<b?a:b) using namespace std; typedef long long ll; typedef pair<int,int> node; int read() { char ch=0;int w=0,ff=1; while(ch<'0'||ch>'9'){if(ch=='-')ff=-1;ch=getchar();} while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();} return ff*w; } int h[MAXX],cnt; struct edge{int to,nex,w;}e[100005]; void add(int u,int to,int w){e[++cnt]=(edge){to,h[u],w},h[u]=cnt;} int map2[MAXX][1<<15],val[MAXX]; int dis[MAXX][1<<15],ans; int n,m,k; void spfa() { memset(dis,0x3f,sizeof(dis)); memset(map2,0,sizeof(map2)); ans=dis[0][0]; int S=(1<<k)-1; queue<node>que; for(int i=1;i<=n;++i){que.push(node(i,1<<val[i])),dis[i][1<<val[i]]=0,map2[i][1<<val[i]]=1;} while(!que.empty()) { node p=que.front();que.pop(); map2[p.first][p.second]=0; for(int i=h[p.first];i;i=e[i].nex) { if((1<<val[e[i].to])&p.second) continue; int goal=(p.second|(1<<val[e[i].to])); if(dis[e[i].to][goal]>dis[p.first][p.second]+e[i].w) { dis[e[i].to][goal]=dis[p.first][p.second]+e[i].w; if(!map2[e[i].to][goal]) map2[e[i].to][goal]=1,que.push(node(e[i].to,goal)); } } } for(int i=1;i<=n;++i) ans=MIN(dis[i][S],ans); } int u,to,w; int main() { r(n),r(m),r(k); for(int i=1;i<=n;++i) r(val[i]); for(int i=1;i<=m;++i) r(u),r(to),r(w),add(u,to,w); spfa(); if(ans!=dis[0][0]) printf("%d",ans); else printf("Ushio!"); return 0; }
光坂小镇是一个由 nn 个点（编号为 11 ~ nn），mm 条有向边构成的图，每个节点上都有一个光玉，光玉共有 kk 种，编号为 00 ~ k-1k−1。
为了使一切改变，朋也需要找齐全部的 kk 种光玉。他可以从任意一个节点出发，在图上任意行走，但不会经过同一个节点两次，每碰到一个光玉便会将其收集，收集到 kk 个光玉后，即经过了 kk 个节点后，便不会继续收集。请设计一种方案，使得朋也能够收集全部的 kk 种光玉，且走过的路径长度最短。
换句话说，每个点一个颜色，找到一条最短的点数为 kk 、恰好经过全部 kk 种颜色的路径。你需要求出这条路径的长度。