牛客练习赛17 -- E（TSP+spfa）

写了好久终于过了，

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
typedef pair<int,int> pii;
/*void dis(int a[], int n){printf("总数为%d个\n",n); for(int i = 0; i < n; i++) 	cout<<a[i]<<", ";cout<<endl<<"------------------"<<endl;		
}*/const int mx = 1e5+10;
const ll inf = 0x3f3f3f3f;
int vis[mx], dis[mx],s[25][25],p[25],dp[25][10005],id[mx];
int n,m,sco;  
/*struct node{  int to, w;  
};*/  
vector<pii> ve[mx];  
queue <int>q; void spfa(int u,int id){  memset(dis, 63, sizeof (dis));  memset(vis, 0, sizeof(vis));  while(!q.empty()) q.pop();  dis[u] = 0;  q.push(u);  vis[u] = 1;  while(!q.empty()){  int x = q.front();  q.pop();  vis[x] = 0;  for(int i = 0; i < ve[x].size(); i++){     pii te= ve[x][i];  if(dis[x] + te.second < dis[te.first]){  dis[te.first] = dis[x] + te.second;  if(!vis[te.first]){  vis[te.first] = 1;  q.push(te.first);  }  }  }  }  for(int i = 0; i <= sco; i++)  s[id][i]=dis[p[i]]; }  int dfs(int u,int sta){
//	printf("sta =%d\n",sta);if(sta == 0)	return s[u][0];if(dp[u][sta] != 0x3f3f3f3f)	return dp[u][sta];for(int i = 1; i <= sco; i++){if((1<<(i-1))&sta)dp[u][sta] = min(dp[u][sta],s[u][i]+dfs(i,sta^(1<<(i-1))));}		return dp[u][sta];
}int main(){int T=10;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i = 0; i <n; i++)      //忘记初始化 ve[i].clear();int a, b, c;pii te;for(int i = 0; i< m; i++){scanf("%d%d%d",&a,&b,&c);te.first = b; te.second = c;ve[a].push_back(te);te.first = a;ve[b].push_back(te);}scanf("%d",&sco);p[0] = 0;id[0] = 0;for(int i = 1; i <= sco; i++){scanf("%d",&p[i]);id[p[i]]  = i;//spfa2(p[i],i);         //不可以在这里一边输入一边spfa }for(int i = 0; i <= sco; i++){spfa(p[i],i);}memset(dp,0x3f3f3f3f,sizeof(dp));   //不能初始化为-1 cout<<dfs(0,(1<<sco)-1)<<endl;}	return 0;
}