好纠结 这么道  破题  比赛是竟然 没做出来  ，比赛 完后  加了个 条件就对了 ，为什么 比赛时 那么 没状态   。。。。。。。。。。。

题意：给出一个无向图  ，一个 原点 s  一个终点  t  求 一条 最短的路径 值 从 s 到 t  ，对于 这条路径  可以 将  其中的 一条边的权值 减半。

 

题解 ：  dij +  枚举

   首先  我们可以 得到 知道   对于 t  来说  最小值  = min(与他 连接的点的 最小值  +  w[i][t],    s 到  i  的 最短距离   +  w[i][t] / 2) ;

 所以 我们 得到 状态方程 

   dp[i] 记录  i  的  最终解  dis[i]记录  最短路径 

 

    设  x  与  i  相连

    dp[i] = min(dp[i] ,min(dp[x] + w[i][x],dis[x]　＋　ｗ[i][x] / 2)) ;

 

  1 #include<cstdio>

  2 #include<cstring>

  3 #include<cmath>

  4 #include<iostream>

  5 #include<algorithm>

  6 #include<

set>

  7 #include<map>

  8 #include<queue>

  9 #include<vector>

 10 #include<

string>

 11 

#define inf 99999999

 12 

#define maxn 1500

 13 

#define CL(a,b) memset(a,b,sizeof(a))

 14 

#define  ll  long long

 15 

//

#define mx 1000010

 16 

using 

namespace std;

 17 

int n , m ;

 18 

int s,t ;

 19 

int dis[maxn],vis[maxn],pre[maxn] ;

 20 

int mat[maxn][maxn] ;

 21 

int dp[maxn] ;

 22 

int solve(

int s,

int t)

 23 {

 24     

int i , j ;

 25     

for(i = 

0;i<= n;i++)

 26     {

 27         dis[i] = mat[s][i] ;

 28     }

 29     dis[s] = 

0 ;

 30 

 31 

 32     CL(vis,

0) ;

 33 

 34 

 35 

 36     

int k ;

 37     

for(i = 

0 ; i < n;i++)

 38     {

 39         

int mi = inf ;

 40         k = 

0 ;

 41         

for(j = 

1 ; j <= n;j++)

 42         {

 43             

if(!vis[j]&& dis[j] != inf && dis[j] < mi)

 44             {

 45                 mi = dis[j] ;

 46                 k =  j ;

 47             }

 48         }

 49 

 50         

if(k == 

0) 

break ;

 51 

 52         vis[k] = 

1 ;

 53 

 54 

 55         

for(j = 

1 ; j <= n;j++)

 56         {

 57             

if(!vis[j] && mat[k][j] != inf && dis[j] > dis[k] + mat[k][j])

 58             {

 59 

 60                 dis[j] = dis[k] +  mat[k][j] ;

 61 

 62             }

 63         }

 64     }

 65 

 66 

 67 

 68 

 69 

 70     

if(dis[t] >= inf) 

return -

1 ;

 71 

 72 

 73     

for(i = 

0; i<= n;i++)

 74     {

 75         dp[i] = mat[s][i];

 76     }

 77 

 78     dp[s] = 

0 ;

 79 

 80     

for(i = 

1; i <= n;i++)

 81     {

 82 

 83         

for(j = 

1; j <= n;j++)

 84         {

 85             

if(j == s||i == j)

continue ;

 86             

if(mat[i][j]!=inf)

 87             {

 88                 dp[j] = min(dp[j],min(dp[i] + mat[i][j] ,dis[i] + mat[i][j]/

2)) ;

 89             }

 90         }

 91     }

 92 

 93     

return dp[t] ;

 94 

 95 

 96 }

 97 

int main()

 98 {

 99     

int i , j,u,v,w  ;

100     

while(scanf(

"

%d%d

",&n,&m)!=EOF)

101     {

102 

103         

for(i = 

0; i <= n;i++)

104         {

105             

for(j = 

0 ; j <= n;j++)

106              mat[i][j] = mat[j][i] = inf ;

107 

108             mat[i][i] = 

0 ;

109         }

110 

111         

for(i = 

0; i < m;i++)

112         {

113             scanf(

"

%d%d%d

",&u,&v,&w);

114             

if(w < mat[u][v])

115             mat[u][v] = mat[v][u] = w ;

116         }

117         scanf(

"

%d%d

",&s,&t) ;

118         

int ans = solve(s,t) ;

119 

120         

if(ans == -

1)printf(

"

No solution\n

");

121         

else

122             printf(

"

%d\n

",ans) ;

123     }

124 }