#include<bits/stdc++.h>#define int long long#define pii pair<int, int>#define pb push_backusingnamespacestd;constintINF=0x3f3f3f3f;constintmaxn=21;vector<int>G[maxn];voidshortestPathLength(){intn,eg;cin>>n>>eg;vector<vector<int>>d(n,vector<int>(n,INF));intu,v,w;for(inti=0;i<eg;i++){cin>>u>>v>>w;u--,v--;d[u][v]=w;d[v][u]=w;G[u].pb(v);G[v].pb(u);}vector<vector<int>>dp(n,vector<int>((1<<n),INF));intans=INF;for(intmask=0;mask<(1<<n);mask++){vector<int>b;for(inti=0;i<maxn;i++){if(mask&(1<<i)){b.pb(i);}}for(inti=0;i<b.size();i++){if(b.size()==1&&b[0]==0){dp[0][mask]=0;}for(intj=0;j<b.size();j++){if(i==j)continue;intv=b[i],u=b[j];dp[v][mask]=min(dp[v][mask],dp[u][mask^(1<<v)]+d[v][u]);}}}intmask=(1<<n)-1;for(inti=1;i<n;i++){ans=min(dp[i][mask]+d[i][0],ans);}if(ans>=INF)cout<<-1<<"\n";elsecout<<ans<<"\n";}signedmain(){shortestPathLength();}
#include<bits/stdc++.h>#define int long longusingnamespacestd;constintN=20;constintM=1000000007;vector<int>G[N];intdp[(1<<N)][N];signedmain(){ios_base::sync_with_stdio(false);cin.tie(0);intn,m;cin>>n>>m;for(inti=0;i<m;i++){intu,v;cin>>u>>v;u--,v--;if(u==v)continue;G[v].push_back(u);}dp[1][0]=1;for(intmask=0;mask<(1<<n);mask++){for(inti=0;i<n;i++){if(mask&(1<<i)){for(intk:G[i]){dp[mask][i]+=dp[mask^(1<<i)][k];}dp[mask][i]%=M;}}}cout<<dp[(1<<n)-1][n-1]<<'\n';}
這時就不能去算沒相鄰的 i, j 兩點的 dis(i, j) 了,直接用輸入給的 adjacency matrix 即可