Aizu 2541
题意：n个岛屿，由m条桥连接，其中有k条是魔法桥，你可以用魔法把他们变成相同长度。求在执行魔法后，两个起点S1和S2到终点T的最短路的最小绝对差。
（1<=n<=1000，1<=m<=2000，1<=k<=100）
S1和S2到T的最短路将会是如 ax+b 的形式。x为相同长度，a为该最短路上魔法桥的个数。
画出所有的直线，现在等价于求多条射线的最低点。
利用线段交暴力即可。
用dij进行预处理，每个点可以得到最多k条直线，暴力求交点的复杂度O(k^2)。
最后要判断最低点，除去dij处理外，复杂度为O(k^3)。
#include <bits/stdc++.h>
using namespace std;
const long long INF=1LL<<60;
const int MAXN=1005;
int n, m, S1, S2, T;
char s[100];
struct edge{int to;long long w;bool type;edge(int to=0, long long w=0, bool type=false):to(to),w(w),type(t