恥ずかしい勘違いをしちゃったっぽいのでプログラムを書いてみる。
#include<stdio.h>
#define MAX 100

int MAT_NUM,matrix[MAX][MAX];//ノード数,行列
int matset[MAX],junjo[MAX];//使用したノードの保存,確定した順序の保存
int max_junjo[MAX],max_value;//最大値を記録した順序,最大値
int branch;//派生した枝の数

search(int deep){
    int i,value;
    deep++;
    if(deep < MAT_NUM-1){//順序が全て確定してないとき
        for(i = 0;i < MAT_NUM;i++){
            if(matset[i] == 0){
                branch++;
                junjo[deep] = i;
                matset[i] = 1;
                search(deep);
                matset[i] = 0;
            }
        }
    }
    else{//順序が全て確定した
        for(i = 1,value=0;i < MAT_NUM;i++) value += matrix[junjo[i-1]][junjo[i]];
        //for(i = 0;i < MAT_NUM;i++) {printf("->%d",junjo[i]);}printf("  value=%d\n",value);//途中経過の表示
        if(value > max_value){
            max_value = value;
            for(i = 0;i < MAT_NUM;i++) max_junjo[i] = junjo[i];
        }
    }
    
    
}
main(){
    
    int i,j;
    
    /***読み込み開始***/
    scanf("%d",&MAT_NUM);
    //始点と終点のセット
    scanf("%d %d",&junjo[0],&junjo[MAT_NUM-1]);
    matset[junjo[0]] = 1;
    matset[junjo[MAT_NUM-1]] = 1;
    //行列のセット
    for(i = 0;i < MAT_NUM;i++){
        for(j = 0;j < MAT_NUM;j++){
            scanf("%d",&matrix[i][j]);
        }
    }
    
    //探索開始
    search(0);
    
    //結果の表示
    printf("枝の数は%d\n",branch);
    printf("%d - %d 間の最長経路は\n",junjo[0],junjo[MAT_NUM-1]);
    for(i = 0;i < MAT_NUM;i++){
        printf("->%d",max_junjo[i]);
    }
    printf("\n最大値は%d\n",max_value);
}

入力はリダイレクトでファイルから。↓のようなフォーマット。
ノード数
始点 終点
以下ノードの行列

5
0 4
2 6 9 4 0 
2 1 7 0 3 
6 5 9 0 5 
6 8 8 3 4 
9 7 1 4 7 

0->1->2->3->4の順序でノードを通るなら
6+7+0+4=17となる。
でもこの全件探索プログラムだとノード数13ぐらいが限界でした。その時点で枝の数1億突破。
枝刈したいけど、どうやったらできるんだー？？？
明日がんばってみよう。

ついでに行列作成プログラム
保存するファイル名、ノードの数、始点終点の入力で↓のようなのランダムに作ってくれます。

5
0 4
2 6 9 4 0 
2 1 7 0 3 
6 5 9 0 5 
6 8 8 3 4 
9 7 1 4 7 


#include <stdio.h>
#include <stdlib.h>

main(){
    int kosu,i,j,begin,end;
    char filename[128];
    FILE *fp;
    
    printf("保存するファイル名は？\n");
    scanf("%s",filename);
    srand(time(NULL));
    printf("ノードの個数は？\n");
    scanf("%d",&kosu);
    printf("始点と終点は？[0〜%d]\n",kosu-1);
    scanf("%d %d",&begin,&end);
    
    fp = fopen(filename,"w");
    
    fprintf(fp,"%d\n%d %d\n",kosu,begin,end);
    for(i=0;i < kosu;i++){
        for(j=0;j < kosu;j++){
            fprintf(fp,"%d ",rand()%10);
        }
        fprintf(fp,"\n");
    }
    
    fclose(fp);
    printf("作成終了");
}