做个淘宝客网站怎么做/网络推广技术外包

众所周知，蒜蒜是一名热爱工作的好员工，他觉得时间就是金钱，做事情总是争分夺秒。

这天晚上，蒜蒜一个人去吃晚饭。不巧的是，吃完饭以后就开始下雨了，蒜蒜并没有带雨伞出来。但是蒜蒜热爱工作，工作使他快乐，他要尽快赶回去写代码。

蒜蒜的公司在中关村，中关村这边地形复杂，有很多天桥、地下通道和马路交错在一起。其中，地下通道是可以避雨的，天桥和马路都没办法避。可以把中关村抽象成为 nnn 个点的地图（顶点编号为 111 到 nnn），其中有 m1m_1m​1​​ 条地下通道，有 m2m_2m​2​​ 条马路或者天桥，其中地下通道的长度为 111。蒜蒜吃饭的地方在 111 点，公司在 nnn 点。当然，蒜蒜虽然爱工作心切，但是他更不想淋很多雨，同时也不想浪费很多时间。于是他折中了一下——在保证他回到公司所走的路程总和小于等于 LLL 的情况下，他希望淋雨的路程和尽量的少。

请你赶紧帮热爱工作的蒜蒜规划一条路径吧，不要再让他浪费时间。

 

 

 

 

#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=108; 
const int INF=0x3f3f3f3f;
int dp[N][100],n,m1,m2,L;
bool vis[N][100];
int head[N],tot;
vector<int>G[N];
struct pnp{int v,w,next;
}e[N*N];
void add(int u,int v,int w){e[tot].v=v,e[tot].w=w,e[tot].next=head[u],head[u]=tot++;
}
struct node{int u,id,w;bool operator < (const node &A)const{return w>A.w;}
};
void dij(){priority_queue<node>Q;dp[1][0]=0;memset(dp,INF,sizeof(dp));memset(vis,0,sizeof(vis)); node p,q;p.u=1,p.id=0,p.w=0;Q.push(p);while(!Q.empty()){p=Q.top();Q.pop();if(vis[p.u][p.id]) continue;vis[p.u][p.id]=1;for(int i=head[p.u];~i;i=e[i].next){int v=e[i].v;if(dp[v][p.id]>p.w+e[i].w) {dp[v][p.id]=p.w+e[i].w;q.u=v,q.id=p.id,q.w=dp[v][p.id];Q.push(q);}}if(p.id==m1) continue;for(int i=0;i<(int)G[p.u].size();++i) {int v=G[p.u][i];if(dp[v][p.id+1]>p.w+1) {dp[v][p.id+1]=p.w+1;q.u=v,q.id=p.id+1,q.w=dp[v][p.id+1];Q.push(q);}}}
}
int main(){int T,x,y,z;for(scanf("%d",&T);T--;){memset(head,-1,sizeof(head));tot=0;for(int i=0;i<=100;++i) G[i].clear();scanf("%d%d%d%d",&n,&m1,&m2,&L);for(int i=0;i<m1;++i) {scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}for(int i=0;i<m2;++i) {scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}dij();int ans=INF;for(int i=0;i<=m1;++i) if(dp[n][i]<=L) ans=min(ans,dp[n][i]-i);printf("%d\n",ans==INF?-1:ans);}
}