题目大意：
给定一个有向图，N个点M条边，有k个特殊点，请问从S出发到T的最短路径(必须经过k个特殊点 全部)
解题思路：
SPFA + dfs
初始化后跑K+1次SPFA 计算出S的单源最短路径&所有特殊点的单源最短路径，用dis[i][j]表示第j个特殊点到i的最短路径，特殊的，dis[i][0]表示S到i的最短路径 然后就爆搜求最优解Accepted code：
注释版：
#include#include #include #include #include #define r(i,a,b) for (register int i=a;i<=b;i++)using namespace std;const long long inf=1e18;struct node { int x,to,l,next;}e[100001];bool v[50001],b[50001];int last[50001];long long d[50001][13],ans;int n,m,k,s,t,cnt;inline int read() { int x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar(); return x;}void add(int x,int y,int z) { e[++cnt].to=y; e[cnt].l=z; e[cnt].next=last[x]; last[x]=cnt;}void init() { memset(last,-1,sizeof(last)); n=read();m=read();k=read();s=read();t=read(); r(i,1,m) { int x=read(),y=read(),z=read(); add(x,y,z); } r(i,1,k) e[i].x=read();}void Spfa(int S,int X) { //SPFA就不说了 queue que; r(i,0,50000) d[i][X]=inf; memset(v,0,sizeof(v)); v[S]=1; que.push(S); d[S][X]=0; while (que.size()) { int x=que.front(); que.pop(); v[x]=0; for (int i=last[x];~i;i=e[i].next) { int y=e[i].to; if (d[y][X]>d[x][X]+e[i].l) { d[y][X]=d[x][X]+e[i].l; if (!v[y]) { v[y]=1; que.push(y); } } } }}void Print(long long x) { //优化输出 if (x>9) Print(x/10); putchar(x%10+48); return;}void dfs(int dep,long long sum,int fa) { if (dep==k) {ans=min(sum+d[t][fa],ans); return;} //如果已经找到了，ans求min值 for (int i=1;i<=k;i++) //遍历下去 if (!b[i]) { b[i]=1;//标记 sum+=d[e[i].x][fa];//求出走这个点的距离之和 dfs(dep+1,sum,i); sum-=d[e[i].x][fa];//为下个点做准备 b[i]=0;//取消标记 }}void Spfa_Main() { Spfa(s,0);//首先求出dis[i][0] for (int i=1;i<=k;i++) Spfa(e[i].x,i);//求出每一个特殊点到所有点的最短路径 ans=inf; dfs(0,0,0); //初始化ans，进入爆搜 if (ans>=inf) printf("-1"); else Print(ans);//如果不能满足条件则输出-1 //否则当然是输出ans啦~}int main() { init();//初始化什么的 Spfa_Main(); return 0;}
无注释版：
#include#include #include #include #include #define r(i,a,b) for (register int i=a;i<=b;i++)using namespace std;const long long inf=1e18;struct node { int x,to,l,next;}e[100001];bool v[50001],b[50001];int last[50001];long long d[50001][13],ans;int n,m,k,s,t,cnt;inline int read() { int x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar(); return x;}void add(int x,int y,int z) { e[++cnt].to=y; e[cnt].l=z; e[cnt].next=last[x]; last[x]=cnt;}void init() { memset(last,-1,sizeof(last)); n=read();m=read();k=read();s=read();t=read(); r(i,1,m) { int x=read(),y=read(),z=read(); add(x,y,z); } r(i,1,k) e[i].x=read();}void Spfa(int S,int X) { queue que; r(i,0,50000) d[i][X]=inf; memset(v,0,sizeof(v)); v[S]=1; que.push(S); d[S][X]=0; while (que.size()) { int x=que.front(); que.pop(); v[x]=0; for (int i=last[x];~i;i=e[i].next) { int y=e[i].to; if (d[y][X]>d[x][X]+e[i].l) { d[y][X]=d[x][X]+e[i].l; if (!v[y]) { v[y]=1; que.push(y); } } } }}void Print(long long x) { if (x>9) Print(x/10); putchar(x%10+48); return;}void dfs(int dep,long long sum,int fa) { if (dep==k) {ans=min(sum+d[t][fa],ans); return;} for (int i=1;i<=k;i++) if (!b[i]) { b[i]=1; sum+=d[e[i].x][fa]; dfs(dep+1,sum,i); sum-=d[e[i].x][fa]; b[i]=0; }}void Spfa_Main() { Spfa(s,0); for (int i=1;i<=k;i++) Spfa(e[i].x,i); ans=inf; dfs(0,0,0); if (ans>=inf) printf("-1"); else Print(ans);}int main() { init(); Spfa_Main(); return 0;}