大臣J從城市4到城市5要花費135的路費。
方法1：由于兩個城市之間僅僅有一種方法到達，是以能夠採用floyd的方法求出随意兩點間的最短距離，由于僅僅有一種方法。然後求出這些最短路徑中的最大值就可以。
可是這樣僅僅能通過75%的資料。
#include
#include
#define inf 1<<10
#define N 101
int dp[N][N];
int main()
{
int n,i,j,k,a,b,d,longest=0,sum=0;
for(i=1;i
for(j=1;j
dp[i][j]=inf;
for(i=1;i
dp[i][i]=0;
scanf("%d",&n);
for(i=0;i
{
scanf("%d%d%d",&a,&b,&d);
dp[a][b]=d;
dp[b][a]=d;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dp[i][j] = dp[i][j]>dp[i][k]+dp[k][j]?dp[i][k]+dp[k][j]:dp[i][j];//floyd算法的模闆
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(dp[i][j]longest)
longest=dp[i][j];
printf("%d\n",longest*(21+longest)/2);
//system("pause");
return 0;
}
方法二：動态規劃
#include
#include
using namespace std;
#define MAXN 100010 //不知n為多大，随便定義了個。能夠定義更大。也能夠想想用vector容器
#define LL long long
int n;
LL Dp[MAXN],Max[MAXN],ans;//全區變量自己主動初始化為0
//鍊式前向星
int head[MAXN],m=1;//由于head[]中元素都為0，是以m從1計數就不用初始化head[]了
struct Edge{
int to,next,w;
}e[MAXN];
//鍊式前向星加入邊
void add_edge(int u,int v,int w){//鄰接表的模闆
e[m].to = v;
e[m].w = w;
e[m].next = head[u];
head[u] = m++;
}
bool f[MAXN];//标記節點是否已被訪問過
void dfs(int s){
int k = head[s];
while(k > 0){
int t = e[k].to;//t為s的孩子節點
if(!f[t]){
f[t] = true;
dfs(t);
Max[s] = max(Max[s] , Dp[s] + Dp[t]+e[k].w);//以s為根節點的子樹中 經過s的最大兩點間距離
Dp[s] = max(Dp[s] , Dp[t]+e[k].w);//s到葉子節點的最長距離
}
k = e[k].next;
}
ans=max(ans,Max[s]);
}
void work(){
f[1]=true;
dfs(1);//以節點1為根節點深搜 。深搜前标記1被訪問
printf("%I64d\n",ans*(21+ans)/2);
}
void init(){
scanf("%d",&n);
int p,q,d;
for(int i = 1 ; i < n ; i++){
scanf("%d%d%d",&p,&q,&d);
add_edge(p,q,d);
add_edge(q,p,d);//雙向邊建圖，友善dfs
}
}
int main()
{
init();
work();
return 0;
}