题目大意：给出一个连通的有向图，求图中顶点1到顶点n的、经过其余顶点一次且仅一次的最短路径及其长度。
解题报告：
考虑到重边，用邻接矩阵判重，稀疏图dfs时用邻接表，省时又给力！
AC代码：
1 #include<bits/stdc++.h> 2 #define numm ch-48 3 #define pd putchar(' ') 4 #define pn putchar(' ') 5 #define pb push_back 6 #define fi first 7 #define se second 8 #define fre1 freopen("1.txt","r",stdin) 9 #define fre2 freopen("3.txt","w",stdout) 10 #define bug cout<<"*******************"<<endl; 11 #define debug(args...) cout<<#args<<"->"<<args<<" "; 12 using namespace std; 13 template <typename T> 14 void read(T &res) { 15 bool flag=false;char ch; 16 while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true); 17 for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm); 18 flag&&(res=-res); 19 } 20 template <typename T> 21 void write(T x) { 22 if(x<0) putchar('-'),x=-x; 23 if(x>9) write(x/10); 24 putchar(x%10+'0'); 25 } 26 typedef long long ll; 27 typedef unsigned long long ull; 28 const int maxn=45; 29 const int maxm=205; 30 const int mod=1e9+7; 31 const int inv2=500000004; 32 const int inf=0x3f3f3f3f; 33 const ll INF=0x3f3f3f3f3f3f3f3f; 34 const int N=32; 35 int a[maxn][maxn]; 36 vector<int>v; 37 int ans[maxn],minans=inf,n,m,head[maxn],cnt=0; 38 bool flag,vis[maxn]; 39 struct node { 40 int v,net,w; 41 }e[maxm]; 42 void addedge(int u,int v,int w) { 43 e[++cnt]=(node){v,head[u],w}; 44 head[u]=cnt; 45 } 46 void dfs(int st,int step,int now) { 47 if(now>=minans) return ; 48 if(step==n&&st==n) { 49 minans=now; 50 flag=true; 51 for(int i=0;i<v.size();i++) 52 ans[i]=v[i]; 53 return ; 54 } 55 for(int i=head[st];~i;i=e[i].net) { 56 int to=e[i].v; 57 if(!vis[to]) { 58 vis[to]=true; 59 v.pb(to); 60 dfs(to,step+1,now+a[st][to]); 61 vis[to]=false; 62 v.pop_back(); 63 } 64 } 65 } 66 int main() 67 { 68 // #define local 69 #ifdef local 70 fre1; 71 fre2; 72 #endif // local 73 read(n),read(m); 74 for(int i=1;i<=n;i++) { 75 head[i]=-1; 76 for(int j=1;j<=n;j++) 77 a[i][j]=inf; 78 } 79 for(int i=1;i<=m;i++) { 80 int u,v,w; 81 read(u),read(v),read(w); 82 a[u][v]=a[u][v]<=w?a[u][v]:w; 83 } 84 for(int i=1;i<=n;i++) 85 for(int j=1;j<=n;j++) 86 if(i!=j&&a[i][j]!=inf) 87 addedge(i,j,a[i][j]); 88 vis[1]=true; 89 dfs(1,1,0); 90 if(!flag) puts("No solution"); 91 else { 92 write(minans);pn; 93 write(1); 94 for(int i=0;i<n-1;i++) 95 pd,write(ans[i]); 96 pn; 97 } 98 return 0; 99 }