17835208153

1065

### 题目描述

1≤n≤500,
1≤m≤105,

#### 样例

输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

6


### prim算法步骤图

#### C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
memset(dist, 0x3f, sizeof dist);

int res = 0;
for (int i = 0; i < n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

if(i && dist[t] == INF)
return INF;
if(i)
res += dist[t];
for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], g[t][j]);

st[t] = true;
}
return res;
}

int main()
{
cin >> n >> m;

memset(g, 0x3f, sizeof g);

for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}

int t = prim();

if (t == INF)
puts("impossible");
else
cout << t << endl;

return 0;
}


#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
memset(dist, 0x3f, sizeof dist);

int res = 0;
for (int i = 0; i < n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

if(i && dist[t] == INF)
return INF;
if(i)
res += dist[t];
for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], g[t][j]);

st[t] = true;
}
return res;
}

int main()
{
cin >> n >> m;

memset(g, 0x3f, sizeof g);

for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}

int t = prim();

if (t == INF)
puts("impossible");
else
cout << t << endl;

return 0;
}


#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 210, INF = 1e9;

int n, m, k;
int d[N][N];

void floyd()
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
cin >> n >> m >> k;

for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i == j)
d[i][j] = 0;
else
d[i][j] = INF;

for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
d[a][b] = min(d[a][b], c);
}

floyd();

for (int i = 0; i < k; i++)
{
int a, b;
cin >> a >> b;
int t = d[a][b];

if (t > INF/2)
cout << "impossible" << endl;
else
cout << d[a][b] << endl;
}
return 0;

}


#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

bool spfa()
{
queue<int> q;

//入队
for (int i = 1; i <= n; i++)
{
st[i] = true;
q.push(i);
}

//出队
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;

for (int i = h[t]; i != -1; i = ne[i])
{
//取出元素
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;

if (cnt[j] >= n)
return true;

if (!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
return false;
}

int main()
{
memset(h, -1, sizeof h);

cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
}

if (spfa())
puts("Yes");
else
puts("No");

return 0;
}



### 题目描述

1≤n≤2000,
1≤m≤10000,

#### 样例

输入样例：
3 3
1 2 -1
2 3 4
3 1 -4

Yes


spfa算法

### 算法思路

1. 将所有结点入队
2. 出队
3. 更新距离，并利用抽屉原理判断是否存在负环
4. 将更新距离后的结点入队

O(nm)

#### C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

bool spfa()
{
queue<int> q;

//入队
for (int i = 1; i <= n; i++)
{
st[i] = true;
q.push(i);
}

//出队
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;

for (int i = h[t]; i != -1; i = ne[i])
{
//取出元素
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;

if (cnt[j] >= n)
return true;

if (!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
return false;
}

int main()
{
memset(h, -1, sizeof h);

cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
}

if (spfa())
puts("Yes");
else
puts("No");

return 0;
}



### 题目描述

1≤n,m≤105,

#### 样例

输入样例：
3 3
1 2 5
2 3 -3
1 3 4

2


### spfa算法（对bellmen_ford算法的优化）

1. 初始化所有点的最短距离为正无穷，将1号点最短距离设为0
2. 设置一个队列来存储更新过距离的点，将一号点入队，st[N]用来判断节点是否已在队列中
3. 每从队列中弹出一个元素，便进行一次迭代
4. 在每一次迭代中，更新弹出元素可以到达的所有节点，如果dist有更新，则把更新过距离且当前不在队列中的结点入队
5. 直到队列中没有元素

blablabla

#### C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

queue<int> q;
q.push(1);

st[1] = true;

while(q.size())
{
int t = q.front();
q.pop();

st[t] = false;

for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
}

int main()
{
memset(h, -1, sizeof h);

cin >> n >> m;

for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
}

spfa();

if (dist[n] == 0x3f3f3f3f)
cout << "impossible" << endl;
else
cout << dist[n] << endl;

return 0;
}


#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

queue<int> q;
q.push(1);

st[1] = true;

while(q.size())
{
int t = q.front();
q.pop();

st[t] = false;

for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
}

int main()
{
memset(h, -1, sizeof h);

cin >> n >> m;

for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
}

spfa();

if (dist[n] == 0x3f3f3f3f)
cout << "impossible" << endl;
else
cout << dist[n] << endl;

return 0;
}


17835208153
1个月前

### 题目描述

1≤n,k≤500,
1≤m≤10000,

#### 样例

输入样例：
3 3 1
1 2 1
2 3 1
1 3 3

3


### bellman_ford算法

1. 初始化，将所有点的距离设为正无穷，将1号点的距离设为0
2. 进行k次迭代，表示从1到n号点最多不经过k条边
3. 在每一次迭代中，先对dist数组备份，然后遍历每一条边
4. 在每一次遍历中，更新经过k条边时，从1号点到所有点的最短距离

km

#### C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int dist[N];
int last[N];

struct Edge
{
int a, b, c;
}edges[M];

void bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 0; i < k; i++)
{
memcpy(last, dist, sizeof dist);
for (int j = 0; j < m; j++)
{
auto e = edges[j];
dist[e.b] = min(dist[e.b], last[e.a] + e.c);
}
}
}

int main()
{
cin >> n >> m >> k;

for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;

edges[i] = {a, b, c};
}

bellman_ford();

if (dist[n] > 0x3f3f3f3f / 2)
cout << "impossible" << endl;
else
cout << dist[n] << endl;

return 0;
}



17835208153
1个月前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int dist[N];
int last[N];

struct Edge
{
int a, b, c;
}edges[M];

void bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 0; i < k; i++)
{
memcpy(last, dist, sizeof dist);
for (int j = 0; j < m; j++)
{
auto e = edges[j];
dist[e.b] = min(dist[e.b], last[e.a] + e.c);
}
}
}

int main()
{
cin >> n >> m >> k;

for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;

edges[i] = {a, b, c};
}

bellman_ford();

if (dist[n] > 0x3f3f3f3f / 2)
cout << "impossible" << endl;
else
cout << dist[n] << endl;

return 0;
}



17835208153
1个月前

### 题目描述

1≤n,m≤1.5×105,

#### 样例

输入样例：
3 3
1 2 2
2 3 1
1 3 4

3


### 算法 堆优化版的dijkstra算法

1. 初始化：将所有点的最短距离设置为+正无穷，将1号点的最短距离设置为0
2. 设置优先队列（堆）， 将1号点入队
3. 进行n次遍历，每次遍历先将堆顶元素弹出，再用这个点更新其他点的距离，将更新距离后的点入队
4. 将堆顶元素弹出，标为已确定最短路的点，如果这个点已经被标记过，则continue

mlogn

#### C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});

while(heap.size())
{
auto t = heap.top();
heap.pop();

int ver = t.second, distance = t.first;

if (st[ver])
continue;
st[ver] = true;

for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f)
return -1;
return dist[n];
}

int main()
{
memset(h, -1, sizeof h);

cin >> n >> m;

for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;