C - Coolest Ski Route关于最长路的一些问题（未完）

 Gym - 102021C （多源）

就以这个题为例子吧

1.floyd

训练时用的floyd，可能因为范围不严吧，也过掉了

#include
#include
#include
using namespace std;
const int N=1010,M=5010;int d[N][N];
int n,m;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()
{memset(d, 0x3f, sizeof d);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);d[u][v]=min(d[u][v],-w);}floyd();int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){ans=min(d[i][j],ans);}}printf("%d",-ans);return 0;
}

2.spfa

#include 
#include 
#include 
#include 
const int N = 5050;
using namespace std;
#define inf 0x3f3f3f3f
int vis[N];
struct edge
{int v, w;
};
vector g[N];
int in[N];
int dis[N];
typedef pair PII;
void spfa(int s)
{memset(vis, 0, sizeof(vis));priority_queue, greater> q;dis[s] = 0, vis[s] = 1;q.push({0, s});while (q.size()){int u = q.top().second;q.pop();vis[u] = 0;for (auto ed : g[u]){int v = ed.v, w = ed.w;if (dis[v] < dis[u] + w){dis[v] = dis[u] + w;if (!vis[v])q.push({dis[v], v});}}}
}
int n, m;
int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++){int u, v, w;scanf("%d%d%d", &u, &v, &w);g[u].push_back(edge({v, w}));in[v]++;//标记入度}int ans = 0;for (int i = 1; i <= n; i++){if (in[i] == 0)//所有的山顶的入度为0{spfa(i);//遍历所有的山顶找最长路for (int j = 1; j <= n; j++){ans = max(ans, dis[j]);}}}printf("%d", ans);return 0;
}

3.dfs（记忆化搜索，必须是无环图）

题目说只能高的连低的，所以没有环。

#include
using namespace std;
//#define int long long
const int N=1e6+10;
int dis[N];
int vis[N];
int mp[1010][1010];
int n,m;
int flag[N];
int dfs(int x)
{if(vis[x])return dis[x];for(int i=1;i<=n;i++){if(mp[x][i]){dis[x]=max(dis[x],dfs(i)+mp[x][i]);}}vis[x]=1;return dis[x];
}
int main()
{  scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);flag[v]=1;if(mp[u][v])mp[u][v]=max(mp[u][v],w);else mp[u][v]=w;}int ans=0;for(int i=1;i<=n;i++){if(!flag[i])ans=max(ans,dfs(i));}printf("%d",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！