学了后面的bellman-ford想用来这道题试试,但答案不对。想问下是bellman算法不能运用于这类题还是我写的有问题?
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010;
const int M = 10010;
int n,m;
int dist[N];
struct Edge
{
int a,b,w;
}edge[M];
void bellman_ford()
{
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
for (int j = 0; j < m; j ++)
{
int a = edge[j].a, b = edge[j].b, w = edge[j].w;
dist[b] = min(dist[b],dist[a] + w);
}
if (dist[n] == 0x3f3f3f3f) cout << -1;
else cout << dist[n];
}
int main()
{
cin >> n >> m;
for (int i = 0 ; i < m; i ++)
{
int x,y,w;
cin >> x >> y >> w;
edge[i].a = x; edge[i].b = y; edge[i].w = w;
}
bellman_ford();
return 0;
}