最短路合集
1.条件类型最短路
题意：n个点，m无向边，n个点有一部分是特殊的点，求从1走到n最短路是多少。并且该最短路满足走过的特殊点不超过K.
分析: 将所有点的状态分离成K个点(K分层图)，表示到当前该点的走过的特殊点有 个。然后跑一遍dij即可。(dis多建一维条件跑dij也可以)
#include<bits/stdc++.h>
#define ll long long
#define inf 0x7f7f7f7f
#define pr pair<ll,ll>
using namespace std;
const int N=4e6+10;
struct node{
int v,len,next;
}a[N*2];
int pre[N],cnt=0;
ll dis[N],vis[N];
void add( int u,int v,int len )
{
// a[cnt].v=v , a[cnt].len=len , a[cnt].next=pre[u];
a[cnt]={ v,len,pre[u] };
pre[u]=cnt++;
}
void init()
{
memset(pre,-1,sizeof(pre)),cnt=0;
}
void dijstra( int s ) // 起点
{
memset( dis,inf,sizeof(dis) );
memset( vis,0,sizeof(vis) );
priority_queue<pr,vector<pr>,greater<pr> > q;
q.push( make_pair(0,s) );
dis[s]=0;
while( q.size() )
{
int u=q.top().second;
q.pop();
vis[u]=1;
for( int i=pre[u];~i;i=a[i].next )
{
int v=a[i].v,len=a[i].len;
if( !vis[v] && dis[v]>dis[u]+len )
{
dis[v]=dis[u]+len;
q.push( make_pair(dis[v],v) );
}
}
}
}
int tag[N];
int main()
{
init();
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for( int i=1;i<=n;i++ ) scanf("%d",&tag[i]);
if( tag[1] ) k--;
if( tag[n] ) k++;
for( int i=1;i<=m;i++ )
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
for( int j=0;j<=k;j++ )
{
if( !tag[b] ) add(a+n*j,b+n*j,c);
if( !tag[a] ) add(b+n*j,a+n*j,c);
}
for( int j=0;j<k;j++ )
{
if( tag[b] ) add(a+n*j,b+n*j+n,c);
if( tag[a] ) add(b+n*j,a+n*j+n,c);
}
}
ll ans=inf;
dijstra(1);
for( int i=1;i<=k+1;i++ ) ans=min(ans,dis[i*n]);
if( ans!=inf ) printf("%lld\n",ans);
else puts("-1");
}2.最短路K次免费(半价都一样)
#include<bits/stdc++.h>
#include<queue>
#define int long long
#define INF 1e18
using namespace std;
inline int read()
{
int f=1,w=0;char s=getchar();
for( ;!isdigit(s);s=='-' && (f=-1),s=getchar());
for( ;isdigit(s);w=w*10+s-48,s=getchar());
return w*f;
}
int dis[200010][60],n,m,p,head[200010],cnt;
// head[i] 路线起始位置索引到 可能到的位置 结合 edge[i]索引
// dis[i][j] i表示到位置i j表示打折次数 dis[i][j]表示最小花费
struct Edge{
int from,to,next,dis;
}edge[1000010];
inline void addedge( int u,int v,int w ) // 存有向网
{
cnt++;
edge[cnt].from=u;
edge[cnt].to=v;
edge[cnt].dis=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
struct node{
int num,dis,tim;
friend bool operator < (node a,node b) //优先级
{
return a.dis>b.dis;
}
};
priority_queue<node> q; // 优先队列
inline void dij(int s)
{
int u,v,w,i,j,k,tim;
dis[s][0]=0;
q.push( (node){s,0,0} );
while( !q.empty() )
{
node front=q.top();
q.pop();
u=front.num; // u表示到位置
tim=front.tim; // tim 表示打折次数
if(tim>p) continue;
if( front.dis>dis[u][tim] ) continue;
for(i=head[u];i;i=edge[i].next ) // 有点bfs的意思
{
v=edge[i].to;
w=edge[i].dis;
if( dis[v][tim]>dis[u][tim]+w )
{
dis[v][tim]=dis[u][tim]+w;
q.push( (node) {v,dis[v][tim],tim} );
}
if( dis[v][tim+1]>dis[u][tim]+edge[i].dis/2 )
{
dis[v][tim+1]=dis[u][tim]+edge[i].dis/2;
q.push( (node) {v,dis[v][tim+1],tim+1} );
}
}
}
return;
}
signed main(){
n=read();m=read();p=read();
int i,j,k,st,ed;st=1;ed=n;
for( i=1;i<=m;i++ )
{
int x,y,z;
x=read();y=read();z=read();
addedge(x,y,z);
}
//// 调试
// cout<<endl;
// for( int i=1;i<=n;i++ )
// {
// // printf("%d ",head[i]);
// for(j=head[i];j;j=edge[j].next )
// {
// printf("%d ",j);
// }cout<<endl;
// }cout<<endl;
//
for( int i=0;i<=200000;i++ ) // 初始化操作
{
for( int j=0;j<=10;j++ )
{
dis[i][j]=INF;
}
}
dij(st);
int ans=INF;
for( int i=0;i<=p;i++ )
{
ans=min( ans,dis[n][i] );
}
if( ans==INF ) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}HDU6797
3.n阶完全图，每条边都有一个边权，你可以去掉k条边，使得最短路的长度尽量长。求最短路最长是多少。
暴力修改最短路上的边，然后跑最短路，迭代k次。答案去最大。
#include<bits/stdc++.h>
#define pr pair<int,int>
typedef long long ll;
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=55;
const int maxm=300;
bool vis[maxn];
int d[maxn],g[maxn][maxn];
int n,m,s,e,path[maxn];
int ans;
void dijkstra()
{
priority_queue<pr> q;
for( int i=1;i<=n;i++ ) d[i]=inf,vis[i]=false;
d[s]=0;
q.push( make_pair(0,s) );
while( !q.empty() )
{
int x=q.top().second;
q.pop();
if( vis[x] ) continue;
vis[x]=true;
for( int v=1;v<=n;v++ )
{
if( !g[x][v] ) continue;
int w=g[x][v];
if( d[v]>d[x]+w )
{
d[v]=d[x]+w;
path[v]=x;
q.push( make_pair(-d[v],v) );
}
}
}
}
void dfs( int x )
{
dijkstra();
if( x==0 )
{
ans=max(ans,d[n]);
return;
}
int j=n,p[55],num=0;
p[++num]=n;
while( path[j] ) // 搜索路径
{
p[++num]=path[j];
j=path[j];
}
for( int i=1;i<num;i++ )
{
int ww=g[p[i]][p[i+1]];
g[p[i]][p[i+1]]=g[p[i+1]][p[i]]=0;
dfs(x-1);
g[p[i]][p[i+1]]=g[p[i+1]][p[i]]=ww;
}
}
int main()
{
int T;
scanf("%d",&T);
while( T-- )
{
ans=0;
int k;
scanf("%d%d",&n,&k);
for( int i=1;i<=n*(n-1)/2;i++ )
{
int u,v,w;scanf("%d%d%d",&u,&v,&w);
g[u][v]=g[v][u]=w;
}
s=1;
dfs(k);
printf("%d\n",ans);
}
}
未完待续
