app开发学习网站,湖北省住房和城乡建设厅门户网站,炫酷特效网站,泉州网站平台建设公司正题
nowcoder 1104-B 题目大意
给你一个无向图#xff0c;问你从1开始经过若干必要边#xff0c;然后回到1的最短路径 解题思路
因为关键边较少#xff0c;先从每个关键点跑一遍dij#xff0c;得出最短距离
设fs,if_{s,i}fs,i表示必要边的状态为s#xff0c;当前在…正题
nowcoder 1104-B 题目大意
给你一个无向图问你从1开始经过若干必要边然后回到1的最短路径 解题思路
因为关键边较少先从每个关键点跑一遍dij得出最短距离
设fs,if_{s,i}fs,i表示必要边的状态为s当前在第i个关键点的最短距离然后直接转移 code
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 50010
#define M 200021
#define mp make_pair
#define fs first
#define sn second
using namespace std;
ll n,m,k,x,y,z,w,tot,ans,p[N],b[N],h[N],q[30],to[30][30],f[50000][30];
priority_queuepairll,ll d;
struct rec
{ll l,to,nx;
}e[M1];
struct node
{node(ll xx0,ll yy0,ll zz0){xxx,yyy,zzz;}ll x,y,z;
}a[30];
void add(ll x,ll y,ll z)
{e[tot].toy;e[tot].lz;e[tot].nxh[x];h[x]tot;return;
}
void dij(ll x)
{memset(b,127/3,sizeof(b));memset(p,0,sizeof(p));b[x]0;d.push(mp(0,x));while(!d.empty()){ll ud.top().sn;d.pop();if(p[u])continue;p[u]1;for(ll ih[u];i;ie[i].nx){ll ve[i].to;if(b[u]e[i].lb[v]){b[v]b[u]e[i].l;d.push(mp(-b[v],v));}}}return;
}
int main()
{scanf(%lld%lld%lld,n,m,k);for(ll i1;im;i){scanf(%lld%lld%lld,x,y,z);if(ik){a[i]node(x,y,z);q[w]x;q[w]y;}add(x,y,z);add(y,x,z);}q[w]1;sort(q1,q1w);wunique(q1,q1w)-q-1;for(ll i1;iw;i){dij(q[i]);//跑最短路for(ll j1;jw;j)to[i][j]b[q[j]];}for(ll i1;ik;i){a[i].xlower_bound(q1,q1w,a[i].x)-q;a[i].ylower_bound(q1,q1w,a[i].y)-q;}memset(f,127/3,sizeof(f));f[0][1]0;for(ll s0;s(1k)-1;s)for(ll i1;ik;i)if(!(s(1i-1)))for(ll j1;jw;j){f[s|(1i-1)][a[i].x]min(f[s|(1i-1)][a[i].x],f[s][j]min(to[j][a[i].y]a[i].z,to[j][a[i].x]a[i].zto[a[i].y][a[i].x]));//有两种走的方法f[s|(1i-1)][a[i].y]min(f[s|(1i-1)][a[i].y],f[s][j]min(to[j][a[i].x]a[i].z,to[j][a[i].y]a[i].zto[a[i].x][a[i].y]));}ans1e15;for(ll i1;iw;i)ansmin(ans,f[(1k)-1][i]to[i][1]);printf(%lld,ans);return 0;
}
