无奈占坑……

这次坑填的倒是挺快的hhh

3890: [Usaco2015 Jan]Meeting Time

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 321  Solved: 175

[][][]

Description

Bessie和她的妹妹Elsie想要从谷仓旅行到他们最喜欢的地区去。她们会在同一时间离开谷仓，也希望要在同一时

间到达她们的目的地地区。农场由N个地区组成，分别编号为1..N (1 <= N <= 100)，谷仓位于1号区域，而她们的

目的地是N号区域。由于农场是依山而建的，两个区域之间会有高度差，编号小的地区海拔高于编号大的地区的海

拔，即1号地区海拔最高，N号地区海拔最低。会有M条小路两两连接不同地区。因为山路过于陡峭，路只允许以下

坡的方式行走。比如就一条路连接了5号区域和8号区域，那么只允许从5号区域前往8号区域而不允许反向行走。每

两个地区之间至多只有一条路，所以M <= N(N-1)/2。Bessie和Elsie走路所花费的时间是不一样的。比如，走同一

条路，Bessie会需要10个单位时间，而Elsie会要20个。请注意，因为她们在赶时间，所以只会在路上花费时间，

进入或者离开一个区域不需要花费时间，而且她们也不会停下来等对方。请帮忙计算出Bessie和Elsie最短需要多

少时间才能同时出发且同时到达她们的目的地。

 

 

Input

第一行包含两个以空格分隔的整数，分别为N和M。

接下来M行描述连接区域之间的路的情况

每一行给出四个以空格分隔的整数A B C D，表示A区域和B区域之间有一条路，

Bessie需要C个单位时间来走完这条路，而Elsie需要D个单位时间来走。

C和D都在区间1..100内。

 

Output

输出一个整数。即Bessie和Elsie同时出发且同时达到N号区域所需要的最少时间。

如果无法到达N号区域或者不可能同时到达，请输出单词 "IMPOSSIBLE"（引号不用输出）。

 

Sample Input

3 3

1 3 1 2

1 2 1 2

2 3 1 2

Sample Output

2

SOLUTION NOTES:

Bessie is twice as fast as Elsie on each path, but if Bessie takes the

path 1->2->3 and Elsie takes the path 1->3 they will arrive at the

same time.

HINT

 

Source

这题本来想练习拓扑排序的……可是貌似看到有大佬用完全背包把尬过去了？？？Orz laj还是太辣鸡了……

竟然交了两次……没看到IMPOSSIBLE直接输出-1了mmp

1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=105; 5 int n,m; 6 int tot,head[MAX],adj[MAX*MAX],next[MAX*MAX],wei[MAX*MAX][2]; 7 int f[MAX][10005],g[MAX][10005]; 8 inline int read(){ 9     int an=0,x=1;char c=getchar();10     while (c<'0' || c>'9') {
    if (c=='-') x=-1;c=getchar();}11     while (c>='0' && c<='9') {an=an*10+c-'0';c=getchar();}12     return an*x;13 }14 void addedge(int u,int v,int w1,int w2){15     tot++;16     adj[tot]=v;17     wei[tot][1]=w1,wei[tot][2]=w2;18     next[tot]=head[u];19     head[u]=tot;20 }21 int main(){22     freopen ("time.in","r",stdin);freopen ("time.out","w",stdout);23     int i,j,k;24     int u,v,w1,w2;25     n=read(),m=read();26     for (i=1;i<=m;i++){27         u=read(),v=read(),w1=read(),w2=read();28         addedge(u,v,w1,w2);29     }30     memset(f,false,sizeof(f)),memset(g,false,sizeof(g));31     f[1][0]=g[1][0]=true;32     for (i=1;i