求图中点1到点n的最长路径
for(int i = 2;i <= n;i++){
if(num[i] == 0) //num[i]用于标记点的入度
q.push(i); //q是队列
}
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = 0;i < a[x].size();i++) //vector<int>a[i] 用于记录出边
{
num[a[x][i]]--;
if(num[a[x][i]] == 0) //当前入度为0，说明1肯定无法到
//达，因此该点的出边也是无效
//边，应当删去
q.push(a[x][i]);
}
}
本人用的是第一种方法，代码如下：
#include<iostream> #include<queue> #include<vector> #include<cstring> using namespace std; const int MAX = 99999999; struct node{ int to; int w; }; int main(){ int n,m; cin >> n >> m; vector<struct node> a[n+1]; int dis[n+1]; int book[n+1] = {0}; memset(dis,MAX,sizeof(dis)); for(int i = 0;i < m;i++){ int x,y,w; cin >> x >> y >> w; a[x].push_back((struct node){y,w}); } queue<int> q; q.push(1); book[1] = 1; dis[1] = 0; while(!q.empty()){ int x = q.front() ; q.pop() ; book[x] = 0; for(int i = 0;i < a[x].size() ;i++){ if(dis[a[x][i].to] == MAX) dis[a[x][i].to] = dis[x]+ a[x][i].w; else if(dis[a[x][i].to] < dis[x]+ a[x][i].w) dis[a[x][i].to] = dis[x]+ a[x][i].w; if(book[a[x][i].to] == 0){ q.push(a[x][i].to); book[a[x][i].to] = 1; } } } if(dis[n] == MAX) cout << -1; else cout << dis[n]; return 0; }
原文：https://www.cnblogs.com/LISIYUWANG/p/13338915.html