图论算法
T1-U502532 找水杯
一道水题，基本上和P4779一样（我连样例都搬过来了，能不一样吗？）
所以呢，你们可以直接用\(Dijikstra\)
1.最初起点到达所有点的距离都是未知的，记作无穷大。
2.在对起点的邻接点进行扫描后发现，起点可以通过某些边抵达一些节点，那么就更新d数组（d[i]用于记录起点s到i之间的已知最短距离），并将更新后的数据（数据形式为一对数值：{距离dis，点p}，代表起点s到点p的目前已知最短距离dis）放入优先队列（一种数据结构，其实就是最小堆，会自动把距离最近的点放在堆顶，方便取用，节省了不断查找最小值的复杂度）。
3.然后不断从优先队列中取数据（取出的点p就相当于已经加入了u集合，因为每次都贪心地取了最近的点，而已经加入u集合的点不需要再重复计算，因此引入vis数组记录该过程），然后将取出的数据中的点p作为中转站，对于图中每个点i都比较当前d数组中记录的d[i]（起点s到i之间的已知最短距离）与d[p]+g[p][i]（g[i][j]是邻接矩阵，代表i到j的距离，d[p]+g[p][i]表示从起点s到点p的距离加上从点p到点i的距离），若d[i]更大，也就意味着七点到i的距离其实并不是最短距离，那么就更新d[i]=d[p]+g[p][i]，并将更新后的数据放入优先队列。
4.不断重复这个过程，将数据不断压入优先数列再不断贪心地取最短路径，直到队列被全部取空为止，算法结束。
你们最好要用个堆优化哦~
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+5;
struct EDGE{
int to,w,pre;
}edge[200005];
int n,m,s;
int u,v,w;
int dis[100005];
int head[100005];
bool book[100005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > heap;
void add(int from,int to,int w,int num){
edge[num].to=to;
edge[num].w=w;
edge[num].pre=head[from];
head[from]=num;
return;
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=n;i++){
dis[i]=inf;
}
dis[s]=0;
heap.push(make_pair(0,s));
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
add(u,v,w,i);
}
while(!heap.empty())
{
int t=heap.top().second;
heap.pop();
if(book[t]==true){
continue;
}
book[t]=true;
for(int i=head[t];i!=0;i=edge[i].pre){
dis[edge[i].to]=min(dis[edge[i].to],dis[t]+edge[i].w);
heap.push(make_pair(dis[edge[i].to],edge[i].to));
}
}
for(int i=1;i<=n;i++){
cout<<dis[i]<<" ";
}
puts("");
return 0;
}
T2-U502556 金银岛
这题单看样例就知道用SPFA，因为里面有负数
我们知道bellman_ford的解法太暴力了，每次都遍历所有的边，聪明的你肯定想到了，其实bellman_ford算法中很多次松弛是没有意义的，因为只有当一个点的前驱结点距离更新时，那么该结点才有可能更新（只是有可能，不一定会更新）。
想到这一点，我们就可以用一个队列queue来存储每次的更新的顶点。先将源点压入队列。
只要队列不空，我们就取出队头，遍历它的所有边，依次更新与它相连的点距离源点的距离。如果该顶点距离源点的距离被更新，将它入队。
说明：
-
st[]数组并不是必须的，没有它也可以，只不过运行时间会慢一点。因为st[]的意义就是防止将已经在队列中的点再次入队，提升代码运行效率。
-
SPFA算法不能用来求解含有负权回路的图。因为如果有负权回路，那么负权回路中的顶点距离源点的距离会不断被更新，因此这些顶点也会不断地入队再出队，形成一个死循环。（因此我们也可以借助SPFA来判断一个图中是否含有负权回路）
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=100010;
int n,m;
int e[N],ne[N],h[N],w[N],d[N],st[N],idx;
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void spfa()
{
queue<int> q;
q.push(1); //将源点压入队列
d[1]=0; //同时将源点距离自己本身的距离置为0
st[1]=1; //由于源点已经入队，所以源点的状态置为1
while(!q.empty()) //只要队列不空，就一直循环下去
{
int t=q.front();
q.pop();
st[t]=0; //由于已经将该顶点取出沪，所以又将该点的状态置为0，方便后续再次入队
for(int i=h[t];i!=-1;i=ne[i]) //遍历与该顶点相连的所有顶点
{
int j=e[i];
if(d[j]>d[t]+w[i])
{
d[j]=d[t]+w[i];
if(!st[j])
{
st[j]=1;
q.push(j); //如果距离被更新且该点不在队列中，就将该点压入队列
}
}
}
}
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h); //邻接表的初始化
memset(d,0x3f,sizeof d); //距离数组的初始化
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
spfa();
if(d[n]==0x3f3f3f3f)
cout<<"impossible"<<endl;
else
cout<<d[n]<<endl;
return 0;
}
T3-U447257 [模板] 有向图的强连通分量
题目不够，别人出的来凑
T4-B3647 【模板】Floyd
为了凑齐Dijikstra、Floyd、SPFA出的
可以理解为不断地消除中间节点k，把 i 和 j 经过中间节点的最短距离更新到 map[i][j]中，
相当于我们在i和j之间直接建立了一条可以用map[i][j]最短路径(把中间节点k消除了)
遍历n次就把所有的中间节点消除了，在任何两个节点 i，j 之间都建立了一条直连的最短路径map[i][j]
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 0x3f3f3f3f;
const int N = 1e2+10;
ll dis[N][N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){
if(i==j)dis[i][j]=0;
else dis[i][j]=INF;
}
int v1,v2;ll w;
for(int i=0;i<m;++i){
cin>>v1>>v2>>w;
// dis[v1][v2]=dis[v2][v1]=w;
//取重边时较小的边
dis[v2][v1]=dis[v1][v2]=min(dis[v1][v2],w);
// dis[v2][v1]=min(dis[v2][v1],w);
}
for(int k=1;k<=n;++k){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if((i!=j)&&(i!=k)&&(j!=k))
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(j>1)cout<<" ";
cout<<dis[i][j];
}
cout<<endl;
}
}
给你们看一下我的100分WA
#include <stdio.h>
#define inf 0x3f3f3f3f
int map[1000][1000];
int main()
{
int k,i,j,n,m;
//读入n和m，n表示顶点个数，m表示边的条数
scanf("%d%d",&n,&m);
//初始化
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(i==j)
map[i][j]=0;
else
map[i][j]=inf;
int a,b,c;
//读入边
for(i=1; i<=m; i++)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b]=c;
map[b][a]=c;//这是一个有向图
}
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(map[i][j]>map[i][k]+map[k][j] )
map[i][j]=map[i][k]+map[k][j];
//输出最终的结果,最终二维数组中存的即使两点之间的最短距离
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
printf("%d ",map[i][j]);
}
printf("\n");
}
return 0;
}