/*
呼呼~只能说语文没学好这道题真心做的累呀23333
一开始看到这道题想都没想就想到了toposort+关键路径(无视语病问题)
然后突然发现好像不是这个意思
仔细一看    突然感觉好像不需要AOV?
或者说不能AOV?
倒是有点像求最长路~
手算一下样例自己找下规律
发现最长路的确是可以的 考虑到n,m都很小
直接可以Floyd求最长路~
对于输入的点和边构成的G(V,E)Floyd更新最长路(注意结点数应该是n+1)
然后一定要注意，我们选择的最长路的起点和终点是固定的，只能是1和n+1
所以就直接输出a[1][n+1]就好啦
对于路径上的点的判断就简单啦~
一个循环找一下所有点,如果有a[1][i]+a[i][n+1]==a[1][n+1]
那么就是路径上的点，输出即可
这道题就做出来了    所以一定要细心不要被一大串的题目弄昏了
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n;
int m;
int a[130][130];

void init()
{
    int x,y,w;
    scanf("%d",&n);     n++;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        a[x][y]=w;
    }
}

void Floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=j)
                    if(a[i][k]>0&&a[k][j]>0)
                        a[i][j]=max(a[i][j],a[i][k]+a[k][j]);
}

void output()
{
    printf("%d\n",a[1][n]);
    for(int i=1;i<=n;i++)
        if(a[1][i]+a[i][n]==a[1][n])
            printf("%d ",i);
}

int main()
{
    init();
    Floyd();
    output();
}
     

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)){
        if (ch == '-')
            f = -1;
            ch = getchar();
    }
    while (isdigit(ch)){
        x = x * 10 + ch -48;
        ch = getchar();
    }
    return x * f;
}

inline void write(int x){
    if (x < 0){
        putchar('-');
        write(-x);
        return;
    }
    if (x >= 10)
        write(x / 10);
    putchar(x % 10 + 48);
    return;
}

inline void writeln(int x){
    write(x);
    puts("");
    return;
}

inline void writesp(int x){
    write(x);
    putchar(' ');
    return;
}

int f[199][199];
signed main(){
    int n = read(), m = read();
    n++;
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= m; ++ i)
    f[read()][read()] = read();
    for (int k = 1; k <= n; ++ k)
        for (int i = 1; i <= n; ++ i)
            if (i != k)
                for (int j = 1; j <= n; ++ j)
                    if (i != j && k != j && f[i][k] && f[k][j])
                        f[i][j] = max(f[i][j], f[i][k] + f[k][j]);
    writeln(f[1][n]);
    for (int i = 1; i <= n; ++ i)
        if (f[1][i] + f[i][n] == f[1][n])
            writesp(i);
    return 0;
}

明显的动态规划

#include<iostream>
#include<string.h>
#include<fstream>
using namespace std;
int n,m,g[105][105]={0};
int main(){
    cin>>n>>m;
     n++;
    for(int i=1;i<=m;++i){
      int a,b,c;
      cin>>a>>b>>c;
      g[a][b]=c;
            }
    for(int k=1;k<=n;++k)
    for(int i=1;i<=n;++i)
    if(i!=k)
    for(int j=1;j<=n;++j)
    if(i!=j&&j!=k&&g[i][k]!=0&&g[k][j]!=0)
    if(g[i][j]<g[i][k]+g[k][j])
    g[i][j]=g[i][k]+g[k][j];
     cout<<g[1][n]<<endl;
    cout<<1;
    for(int i=2;i<=n;++i)
    if(g[1][i]+g[i][n]==g[1][n])
    cout<<" "<<i;
    cout<<endl; 
    return 0;
 } 

/*
蒟蒻的思路：
1.先跑一遍Floyd求出完成整个游戏需要至少多长时间；
2.因为游戏总是要开始的，所以肯定是有 “1 ”，所以再输出 “1 ”；
3.因为在跑Floyd的时候已经求出了每个环节完成的最小值，所以只要判断是否符合ed[1][i]加上ed[i][n+1]即可；
以下代码......
*/

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ed[100][100];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,a,b,c;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        ed[a][b]=c;
    }
    for(int k=1;k<=n+1;k++)
        for(int i=1;i<=n+1;i++)
            for(int j=1;j<=n+1;j++){
                if(i!=j&&j!=k&&ed[i][k]&&ed[k][j])
                if(ed[i][j]<ed[i][k]+ed[k][j])
                ed[i][j]=ed[i][k]+ed[k][j];
            }
    printf("%d\n",ed[1][n+1]);
    printf("1 "); 
    for(int i=2;i<=n+1;i++)
        if(ed[1][i]+ed[i][n+1]==ed[1][n+1])
            printf("%d ",i);
    return 0;       
}

var n,m,i,x,y,z,j,k:longint;
a:array[0..300,0..300] of longint;
begin
readln(n);
readln(m);
fillchar(a,sizeof(a),0);
for i:=1 to m do
begin
read(x,y,z);
a[x,y]:=z;
end;
for k:=1 to n+1 do
for i:=1 to n+1 do if (i<>k) then
for j:=1 to n+1 do
if (a[i,k]+a[k,j]>a[i,j])and(i<>j)and(j<>K)and(a[i,k]<>0)and(a[k,j]<>0) then a[i,j]:=a[i,k]+a[k,j];
writeln(a[1,n+1]);
write(1,' ');
for i:=2 to n do
if a[1,i]+a[i,n+1]=a[1,n+1] then write(i,' ');
write(n+1);
end.

Accepted

状态 耗时 内存占用

#1 Accepted 0ms 1016.0KiB
#2 Accepted 0ms 1012.0KiB
#3 Accepted 0ms 1012.0KiB
#4 Accepted 0ms 1020.0KiB
#5 Accepted 0ms 1016.0KiB
#6 Accepted 0ms 1008.0KiB
#7 Accepted 0ms 1016.0KiB
#8 Accepted 0ms 1012.0KiB
#9 Accepted 0ms 1016.0KiB
#10 Accepted 0ms 1020.0KiB

这题有点奇怪啊。题意有点模糊，估计是语文不及格的原因。
两条路长度一样的时候被坑了一波，要把两条路上的点都输出。

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 101;
int map[MAXN][MAXN];
int dis[MAXN];
int vis[MAXN];
int ans[MAXN];
int n;

void SPFA() {
    int u = 1;
    dis[u] = 0;
    queue<int> Q;
    Q.push(u);
    vis[u] = 1;
    int i; int temp;
    while (!Q.empty()) {
        u = Q.front();
        Q.pop();
        vis[u] = 0;
        for (i = 1; i <= n + 1; i++) {
            if (map[u][i] != 0) {
                temp = dis[u] + map[u][i];
                if (temp > dis[i]) {
                    dis[i] = temp;
                    if (!vis[i]) {
                        Q.push(i);
                        vis[i] = 1;
                    }
                }
            }
        }
    }
}

int len = 0;
void traceback() {
    ans[len++] = n + 1;
    vis[n + 1] = 1;
    for (int i = 0; i < len; i++) {
        for (int j = 1; j <= n + 1; j++) {
            if (vis[j] || map[j][ans[i]] == 0) continue;
            if (dis[ans[i]] == dis[j] + map[j][ans[i]]) {
                ans[len++] = j;
                vis[j] = 1;
            }
        }
    }
    sort(ans, ans+len);
}

int main() {
    int m;
    scanf("%d%d", &n, &m);
    int i, j;
    for (i = 1; i <= n + 1; i++) {
        vis[i] = 0;
        dis[i] = 0;
        for (j = 1; j <= n + 1; j++)
            map[i][j] = 0;
    }
    int a, b;
    for (i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        scanf("%d", &map[a][b]);
    }
    SPFA();
    traceback();
    printf("%d\n%d", dis[n + 1], ans[0]);
    for (i = 1; i < len; i++)
        printf(" %d", ans[i]);
    return 0;
}

状态 耗时 内存占用

#1 Accepted 4ms 372.0KiB
#2 Accepted 4ms 256.0KiB
#3 Accepted 3ms 216.0KiB
#4 Accepted 3ms 256.0KiB
#5 Accepted 3ms 384.0KiB
#6 Accepted 3ms 352.0KiB
#7 Accepted 3ms 256.0KiB
#8 Accepted 3ms 328.0KiB
#9 Accepted 3ms 376.0KiB
#10 Accepted 3ms 356.0KiB

测试数据 #0: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1164 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1164 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1164 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1164 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1164 KiB, score = 10
Accepted, time = 0 ms, mem = 1168 KiB, score = 100
代码
var n,m,i,x,y,z,j,k:longint;
a:array[0..300,0..300] of longint;
begin
readln(n);
readln(m);
fillchar(a,sizeof(a),0);
for i:=1 to m do
begin
read(x,y,z);
a[x,y]:=z;
end;
for k:=1 to n+1 do
for i:=1 to n+1 do if (i<>k) then
for j:=1 to n+1 do
if (a[i,k]+a[k,j]>a[i,j])and(i<>j)and(j<>K)and(a[i,k]<>0)and(a[k,j]<>0) then a[i,j]:=a[i,k]+a[k,j];
writeln(a[1,n+1]);
write(1,' ');
for i:=2 to n do
if a[1,i]+a[i,n+1]=a[1,n+1] then write(i,' ');
write(n+1);
end.
floyd算法ac。

评测状态    Accepted
题目  P1027 休息中的小呆
递交时间    2016-09-06 14:02:34
代码语言    C++
评测机 ShadowShore
消耗时间    30 ms
消耗内存    632 KiB
评测时间    2016-09-06 14:02:36
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 624 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 632 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 628 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 632 KiB, score = 10
Accepted, time = 30 ms, mem = 632 KiB, score = 100
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int map[131][131]={0},sum[102],l=1;
int n,m;
int main()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        map[a][b] = w;
    }
    for (int k=1;k<=n+1;k++)
        for (int i=1;i<=n+1;i++)
            if (k != i)
            for (int j=1;j<=n+1;j++)
            if (map[i][k] != 0 && map[k][j] != 0 &&i != j && j != k)
                map[i][j] = max(map[i][j],map[i][k]+map[k][j]);
    cout<<map[1][n+1]<<endl;
    cout<<1<<" ";
    for (int i=2;i<=n;i++)
        if (map[1][i] + map[i][n+1] == map[1][n+1])
        cout<<i<<" ";
    cout<<n+1<<endl;
    return 0;
}

水水的

我的题解

http://accepted.com.cn/vijos1027/

为什么搜索80分……无力check
var n,m,i,j,k,a,b,c:longint;
f:array[0..200,0..200] of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;

begin
readln(n);
readln(m);
for i:=1 to m do
begin
readln(a,b,c);
f[a,b]:=c;
end;
for k:=1 to n+1 do
for i:=1 to n+1 do
if i<>k then
for j:=1 to n+1 do
if (j<>k) and (i<>j) then
if (f[i,k]<>0) and (f[k,j]<>0) then

f[i,j]:=max(f[i,k]+f[k,j],f[i,j]);
writeln(f[1,n+1]);
write(1,' ');
for i:=2 to n do
if f[1,i]+f[i,n+1]=f[1,n+1] then
write(i,' ');
writeln(n+1);
end.
NOIP2014赛前AC留念~~~~~~~~
为什么只有floyd才能过？
var n,m,i,j,k,a,b,c:longint;
f:array[0..200,0..200] of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;

begin
readln(n);
readln(m);
for i:=1 to m do
begin
readln(a,b,c);
f[a,b]:=c;
end;
for k:=1 to n+1 do
for i:=1 to n+1 do
if i<>k then
for j:=1 to n+1 do
if (j<>k) and (i<>j) then
if (f[i,k]<>0) and (f[k,j]<>0) then

f[i,j]:=max(f[i,k]+f[k,j],f[i,j]);
writeln(f[1,n+1]);
write(1,' ');
for i:=2 to n do
if f[1,i]+f[i,n+1]=f[1,n+1] then
write(i,' ');
writeln(n+1);
end.

咦？没人和我一样写dfs么..

乍一看想起了关键路径……准备拓扑排序……
忽然一想不是……是FLoyed

floyed的确很爽…………
测试数据 #0: Accepted, time = 78 ms, mem = 940 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 936 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 940 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 940 KiB, score = 10

测试数据 #4: Accepted, time = 7 ms, mem = 940 KiB, score = 10

测试数据 #5: Accepted, time = 31 ms, mem = 940 KiB, score = 10

测试数据 #6: Accepted, time = 7 ms, mem = 936 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 936 KiB, score = 10

测试数据 #8: Accepted, time = 7 ms, mem = 940 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 940 KiB, score = 10

Summary: Accepted, time = 190 ms, mem = 940 KiB, score = 100

代码
program P1027;
var
i,j,k,n,m,x:longint;
f:array[1..200,1..200] of longint;
function max(x,y:longint):longint;
begin
if x>y then
max:=x
else max:=y;
end;
procedure floyed;
begin
for k:=1 to n+1 do
for i:=1 to n+1 do
if k<>i then
for j:=1 to n+1 do
if (f[i,k]<>0) and (f[k,j]<>0) and (i<>j) and (j<>k) then
f[i,j]:=max(f[i,j],f[i,k]+f[k,j]);
end;
Begin
readln(n);
readln(m);
for x:=1 to m do
begin
readln(i,j,k);
f[i,j]:=k;
end;
floyed;
writeln(f[1,n+1]);
write(1);
for i:=2 to n do
if (f[1,i]+f[i,n+1]=f[1,n+1]) then
write(' ',i);
writeln(' ',n+1);
end.

点击查看程序源码+详细题解

• -, 这种题目描述也能有环啊..

‘输出数据比标准答案长’的是因为【末尾不得有多余空格】

╮(╯▽╰)╭

原来FLOYD还可以求最长路

今天真是长见识了

乍一看想起了关键路径……准备拓扑排序……

忽然一想不是……是FLoyed