洛谷P4568题解
hdu3499题解
用一张图解释
就是把free的路线进行分层计算到这个点的距离最小是多少，假设点为pos
mindis=min(mindis,dis[pos+i*n]);0<=i<=free n是多少个点
题意：
在一个带权无向图，n个点，m条边，k个权力（使得一条边权变成0）
再给起始位和终点位，给m条边的u，v，w的信息，求最少路费
思路：
m小于等于50000，k小于等于10，链式前向星的话需要2*2*（10+1）（双向*建零边和带权边（k+1层））
因为当i==k的时候，权力是0，所以不用建第k层的零边的
用dijkstra跑就行了
#include<bits/stdc++.h> using namespace std; #define ll long long #define il inline #define it register int #define inf 0x3f3f3f3f #define lowbit(x) (x)&(-x) #define pii pair<int,int> #define mak(n,m) make_pair(n,m) #define mem(a,b) memset(a,b,sizeof(a)) #define mod 998244353 const int maxn=5e4*44; int n,m,k,tot,s,t; int head[maxn],dis[maxn],vis[maxn]; struct node{int to,w,next;}edge[maxn]; il void add(int u,int v,int w){ edge[tot].to=v;edge[tot].w=w; edge[tot].next=head[u];head[u]=tot++; } il void dijkstra(){ priority_queue<pii,vector<pii>,greater<pii> >q; dis[s]=0;q.push({dis[s],s});//q.push(mak(dis[s],s)); while(!q.empty()){ int now=q.top().second; q.pop(); if(vis[now])continue;vis[now]=1; for(it i=head[now];~i;i=edge[i].next){ int v=edge[i].to; if(!vis[v] && dis[v]>dis[now]+edge[i].w){ dis[v]=dis[now]+edge[i].w; q.push({dis[v],v}); } } } } int main(){ while(~scanf("%d%d%d",&n,&m,&k)){ scanf("%d%d",&s,&t); for(it i=0;i<maxn;i++){ head[i]=-1;dis[i]=inf;vis[i]=0; }tot=0; for(it i=0;i<m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); for(it i=0;i<=k;i++){ add(u+i*n,v+i*n,w); add(v+i*n,u+i*n,w); if(i!=k){ add(u+i*n,v+(i+1)*n,0); add(v+i*n,u+(i+1)*n,0); } } } dijkstra();int ans=inf; for(it i=0;i<=k;i++){ ans=min(ans,dis[t+i*n]); } printf("%d ",ans); } return 0; }
题意：
在一个带权无向图，n个点，m条边
给m条边的u，v，w的信息，可以有一个权力使得一条边的路费减半
再给起始位和终点位，求最少路费
思路：
分两层最短路，因为是很早之前的代码，贼青涩……
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<string> #include<vector> #include<queue> #include<functional> #pragma warning(disable:4996) using namespace std; const int maxn = 200010; #define inf 0x3f3f3f3f3f3f3f #define mem(k,b) memset(k,b,sizeof(k)) #define pi pair<int,int> #define mak(n,m) make_pair(n,m) #define ll long long vector<pi> g[maxn]; ll a[maxn]; bool vis[maxn]; map<string, int>mp; int i, j, k, n, l, m, s, t, w; string p, q; struct cmp2 { bool operator()(const pi a,const pi b){ return a.second > b.second; } }; /*struct cmp2{ friend bool operator<(const pi a, const pi b){ return a.second > b.second; } };*/ inline void di(int s){ priority_queue<pi, vector<pi>, cmp2 >q; a[s] = 0; q.push(mak(s, 0)); while (!q.empty()) { pi tmp = q.top(); q.pop(); int u = tmp.first; if (vis[u]){ continue; } vis[u] = true; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i].first; int w = g[u][i].second; if (a[v] > a[u] + w) { a[v] = a[u] + w; q.push(mak(v, a[v])); } } } } int main() { while (~scanf("%d%d", &n, &m)){ int nn = n << 1; for (int i = 0; i <= nn; i++){ g[i].clear(); a[i] = inf; vis[i] = false; } mp.clear(); int t1 = 1; for (int i = 0; i < m; i++){ cin >> q >> p; scanf("%d", &t); if (mp[p] == 0){ mp[p] = t1; t1++; } if (mp[q] == 0){ mp[q] = t1; t1++; } g[mp[q]].push_back(mak(mp[p], t)); g[mp[q]].push_back(mak(mp[p] + n, t / 2)); g[mp[q] + n].push_back(mak(mp[p] + n, t)); } cin >> q >> p; if (mp[p] == 0){ mp[p] = t1++; } if (mp[q] == 0){ mp[q] = t1++; } int kai = mp[q], jie = mp[p]; di(kai); ll ans = (a[jie], a[jie + n]); if (ans == inf){ printf("-1 "); } else{ printf("%lld ", ans); } } return 0; }
模板 返回顶部
#define ll long long #define il inline #define it register int #define inf 0x3f3f3f3f #define lowbit(x) (x)&(-x) #define pii pair<int,int> #define mak(n,m) make_pair(n,m) #define mem(a,b) memset(a,b,sizeof(a)) #define mod 998244353 int n,m,k,tot,s,t; int head[maxn],dis[maxn],vis[maxn]; struct node{int to,w,next;}edge[maxn]; il void add(int u,int v,int w){ edge[tot].to=v;edge[tot].w=w; edge[tot].next=head[u];head[u]=tot++; } il void dijkstra(){ priority_queue<pii,vector<pii>,greater<pii> >q; dis[s]=0;q.push({dis[s],s});//q.push(mak(dis[s],s)); while(!q.empty()){ int now=q.top().second; q.pop(); if(vis[now])continue;vis[now]=1; for(it i=head[now];~i;i=edge[i].next){ int v=edge[i].to; if(!vis[v] && dis[v]>dis[now]+edge[i].w){ dis[v]=dis[now]+edge[i].w; q.push({dis[v],v}); } } } } scanf("%d%d%d",&u,&v,&w); for(it i=0;i<=k;i++){ add(u+i*n,v+i*n,w); add(v+i*n,u+i*n,w); if(i!=k){ add(u+i*n,v+(i+1)*n,0); add(v+i*n,u+(i+1)*n,0); } }