C
#include <stdio.h>
#include <string.h>
#define N 510
#define M 10010
#define INF 0x3f3f3f3f
#define min(a,b) ((a)<(b)?(a):(b))
int n, m, k, dist[N], backup[N];
struct Edge {
int from, to;
int weight;
} edges[M];
void init() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; ++i) {
scanf("%d%d%d", &edges[i].from, &edges[i].to, &edges[i].weight);
}
memset(dist, 0x3f, sizeof(dist));
}
int BellmanFord(int start, int end) {
dist[start] = 0;
for (int i = 0; i < k; ++i) {
memcpy(backup, dist, sizeof(dist));
for (int j = 0; j < m; ++j) {
int from = edges[j].from, to = edges[j].to, w = edges[j].weight;
dist[to] = min(dist[to], backup[from] + w);
}
}
return dist[end] < INF/2 ? 1 : 0;
}
int main() {
init();
if (BellmanFord(1, n)) {
printf("%d\n", dist[n]);
} else {
puts("impossible");
}
return 0;
}
C++
#include <iostream>
#include <vector>
using namespace std;
const int MAXSIZE = 510;
const int INF = 0x3f3f3f3f;
int n, m, k;
vector<vector<pair<int, int> > > graph(MAXSIZE, vector<pair<int, int> >());
vector<int> dist(MAXSIZE, INF), backup(MAXSIZE);
bool BellmanFord(int start, int end) {
dist[start] = 0;
for (int i = 0; i < k; ++i) {
backup = dist;
for (int u = 1; u <= n; ++u) {
for (const auto [w, v] : graph[u]) {
dist[v] = min(dist[v], backup[u] + w);
}
}
}
return dist[end] < INF/2;
}
void addEdge(int from, int to, int weight) {
graph[from].emplace_back(weight, to);
}
void init() {
int x, y, z;
cin >> n >> m >> k;
while (m--) {
cin >> x >> y >> z;
addEdge(x, y, z);
}
}
int main() {
init();
if (BellmanFord(1, n)) {
cout << dist[n] << endl;
} else {
cout << "impossible" << endl;
}
return 0;
}
Go
package main
import "fmt"
type Edge struct {
from, to, weight int
}
const INF = 0x3f3f3f3f
var (
n, m, k int
dist, backup []int
edges []Edge
)
func init() {
fmt.Scan(&n, &m, &k)
dist, backup = make([]int, n+1), make([]int, n+1)
for i := 0; i < len(dist); i++ {
dist[i] = INF
}
edges = make([]Edge, m)
for i := 0; i < len(edges); i++ {
fmt.Scan(&edges[i].from, &edges[i].to, &edges[i].weight)
}
}
func BellmanFord(start, end int) bool {
dist[start] = 0
for i := 0; i < k; i++ {
copy(backup, dist)
for j := 0; j < len(edges); j++ {
from, to, w := edges[j].from, edges[j].to, edges[j].weight
if backup[from]+w < dist[to] {
dist[to] = backup[from] + w
}
}
}
return dist[end] < INF/2
}
func main() {
if BellmanFord(1, n) {
fmt.Println(dist[n])
} else {
fmt.Println("impossible")
}
}