之前写过这类型的题目，为什么比赛的时候就脑抽了呢，
因为要最短的改动达到目的，所以我们可以这样想，利用dis【a】【b】来表示改动了b条边到达a点。那么对于原图中的边其实我们还加了一些边。
如原图中a与c相连，我们还加了dis【c】【b+1】与即dis【a】【b】的边，这条边的权值为0，只不过这条边必须在有了dis【a】【b】之后才能添加。
然后遍历dis【n】【i】就可以了。。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#define maxn 1000
#define inf ~0U>>1;
using namespace std;
int n,m,cost;
vector<int>node[maxn];
int map[maxn][maxn];
int visit[maxn][maxn];
int dis[maxn][maxn];
void init()
{
int a,b,c;
memset(map,0,sizeof(map));
for(int i=0;i<=n;i++)
node[i].clear();
for(int i=0;i<m;i++)
{
cin>>a>>b>>c;
node[a].push_back(b);
map[a][b]=c;
}
}
void solve()
{
queue<pair<int,int> >q;//要留空格
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
dis[i][j]=inf;
memset(visit,0,sizeof(visit));
dis[1][0]=0;
q.push(make_pair(1,0));
visit[1][0]=1;
while(!q.empty())
{
int a=q.front().first,b=q.front().second;
q.pop();//出队
for(int i=0;i<node[a].size();i++)
//if(!visit[node[a][i]][b])
{
if(dis[node[a][i]][b]>dis[a][b]+map[a][node[a][i]])
{
dis[node[a][i]][b]=dis[a][b]+map[a][node[a][i]];//能松弛就松弛
if(!visit[node[a][i]][b])//只要不在队列中才加入队列中
{
visit[node[a][i]][b]=1;
q.push(make_pair(node[a][i],b));
}
}
if(dis[node[a][i]][b+1]>dis[a][b])
{
dis[node[a][i]][b+1]=dis[a][b];
if(!visit[node[a][i]][b+1])
{
visit[node[a][i]][b+1]=1;
q.push(make_pair(node[a][i],b+1));
}//队列是push
}
}
visit[a][b]=0;//出队标记
}
for(int i=0;i<=n;i++)
if(dis[n][i]<=cost)
{cout<<i<<endl;break;}
}
int main()
{
while(cin>>n>>m>>cost)
{
if(!(n+m+cost))break;
init();
solve();
}
return 0;
}