洛谷P 3371&&P 4849単源最短【テンプレート】
7320 ワード
最短ルートは図論部分でよくクマの子供の部分で、一般的にdpと一緒に試験します.
図の上ですべての点の最短の経路まで指定することを求めます
洛谷P 3371を例とするアドレスhttps://www.luogu.org/problemnew/show/P3371
最もよく使われる方法は
Floyd複雑度O(n^3);
floydのプロセスは,各点に対して三角形緩和動作を行うことに相当する.すなわち,a−>b+b−>c>a−>cであれば,明らかにa−>b−>cよりa−>cの方が優れ,その後はなくなった.
目測が通らない
図の上ですべての点の最短の経路まで指定することを求めます
洛谷P 3371を例とするアドレスhttps://www.luogu.org/problemnew/show/P3371
最もよく使われる方法は
Floyd複雑度O(n^3);
floydのプロセスは,各点に対して三角形緩和動作を行うことに相当する.すなわち,a−>b+b−>c>a−>cであれば,明らかにa−>b−>cよりa−>cの方が優れ,その後はなくなった.
目測が通らない
//By AcerMo
#include
#include
#include
#include
#include
#include
using namespace std;
int a[5000][5000],n,m,st;// , RE
inline int read()
{
int x=0;char ch=getchar();
while (ch>'9'||ch='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
inline void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
{
if(i==k||a[i][k]==2147483647) continue;//
for(int j=1;j<=n;j++)
{
if(i==j||j==k||a[k][j]==2147483647) continue;
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);// i j i k j min
}
}
return ;
}
signed main()
{
n=read(),m=read(),st=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=2147483647;//
for(int i=1,u,v,w;i<=m;i++)
{
u=read(),v=read(),w=read();
a[u][v]=min(a[u][v],w);
}
a[st][st]=0;floyd();
for(int i=1;i<=n;i++) printf("%d ",a[st][i]);
return 0;
}
Dijkstra O(n^2)
：
，
//By AcerMo
#include
#include
#include
#include
#include
#include
using namespace std;
const int inf=2147483647;
const int M=200500;
int m,n,st;
int dis[M];// i QAQ
bool jud[M];//
//0-> ， ，1-> ，
int to[M],nxt[M],head[M],w[M],cnt;
inline int read()
{
int x=0;char ch=getchar();
while (ch>'9'||ch='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
inline void add(int x,int y,int z)
{
to[++cnt]=y;nxt[cnt]=head[x];w[cnt]=z;head[x]=cnt;
return ;
}
inline void dijkstra()
{
fill(jud,jud+n+1,1);//1 ， =-=
fill(dis,dis+n+1,inf);//
dis[st]=0;// 0
while (1)//
{
int v=-1;
for (int i=1;i<=n;i++)
if ((v==-1||dis[v]>dis[i])&&jud[i]) v=i;//
if (v==-1) break; //
jud[v]=0;//
for (int i=head[v];i;i=nxt[i])
dis[to[i]]=min(dis[to[i]],dis[v]+w[i]);
}
return ;
}
signed main()
{
n=read();m=read();st=read();int x,y,z;
for (int i=1;i<=m;i++)
x=read(),y=read(),z=read(),add(x,y,z);
dijkstra();
for (int i=1;i<=n;i++) printf("%d ",dis[i]);
return 0;
}
Dijkstra ， O（nlogn）;
O(n) ，
//By AcerMo
#include
#include
#include
#include
#include
#include
using namespace std;
const int M=1000500;
struct heap
{
int to,cost;
bool friend operator < (heap a,heap b)
{
return a.cost>b.cost;
}
}add,now;
priority_queueq;
int n,m,st;
int dis[M],vis[M];
int to[M],nxt[M],head[M],w[M],cnt;
inline int read()
{
int x=0;char ch=getchar();
while (ch>'9'||ch='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
inline void adda(int x,int y,int z)
{
to[++cnt]=y;nxt[cnt]=head[x];w[cnt]=z;head[x]=cnt;
return ;
}
inline void dijkstra()
{
fill(dis,dis+n+1,2147483647);dis[st]=0;
add.to=st;add.cost=0;q.push(add);
while (q.size())
{
now=q.top();q.pop();
if (vis[now.to]||dis[now.to]!=now.cost) continue;vis[now.to]=1;
for (int i=head[now.to];i;i=nxt[i])
{
if (dis[to[i]]>dis[now.to]+w[i])
{
dis[to[i]]=dis[now.to]+w[i];
add.to=to[i];add.cost=dis[to[i]];q.push(add);
}
}
}
return ;
}
signed main()
{
n=read();m=read();st=read();int x,y,z;
for (int i=1;i<=m;i++)
x=read(),y=read(),z=read(),adda(x,y,z);
dijkstra();
for (int i=1;i<=n;i++) printf("%d ",dis[i]);
return 0;
}
Bellman-Ford O（NE） TLE
Floyd， ， ， ；
//By AcerMo
#include
#include
#include
#include
#include
#include
using namespace std;
const int M=500500;
int n,m,st;
int dis[M],u[M],v[M],w[M];
inline int read()
{
int x=0;char ch=getchar();
while (ch>'9'||ch='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
inline int Bellman_Ford()
{
dis[st]=0;bool check=0,flag=0;
for(int k=1;k<=n-1;k++) //Bellman-Ford
{
for(int i=1;i<=m;i++)
if((long long)dis[u[i]]+w[i]
O(NE) ？NO！ SPFA ， Bellman-Ford ， O（KE）， ， ， 8102 ， heap+dij
SPFA O（KE）
， ， ，
//By AcerMo
#include
#include
#include
#include
#include
#include
using namespace std;
const int M=500500;
struct edge{int to,cost;}t;
int dis[M],vis[M];
int n,m,st;
vectorv[M];//
inline int read()
{
int x=0;char ch=getchar();
while (ch>'9'||ch='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
inline void SFPA()
{
fill(dis,dis+n+1,2147483647);//fill memset，
dis[st]=0;queueq;q.push(st);
while(q.size())//
{
int u=q.front();q.pop();vis[u]=0;//
for(int i=0;idis[u]+pay)//
{
dis[go]=dis[u]+pay;
if(!vis[go])//
vis[go]=1,q.push(go);
}
}
}
return ;
}
int main()
{
n=read();m=read();st=read();int x;
for(int i=1;i<=m;i++)
{
x=read();t.to=read();t.cost=read();
v[x].push_back(t);
}
SFPA();
for (int i=1;i<=n;i++) printf("%d ",dis[i]);
return 0;
}
；
PS Floyd，Dijkstra