Sachverhalt: A. Die Oberalpstrasse (Kantonsstrasse) ist Teil der Ost-/Westachse des schweizerischen Hauptstrassennetzes. Als Durchgangsstrasse dient sie unter anderem der Erschliessung der Surselva. Bei der Gemeinde Schluein entspricht sie den heutigen Anforderungen nicht mehr. So ist der Innerortsbereich stellenweise sehr eng und unübersichtlich. In einem schlechten Zustand sind die Schleuisertobelbrücke und die Unterführung "Haus Camenisch". Schliesslich ist die Einfahrt in die Oberalpstrasse beim Anschluss Sagogn in Richtung Laax (d.h. in östliche Richtung) heute nur unter Benutzung der Gegenfahrbahn möglich. Die geplante Strassenkorrektion sieht daher in der Gemeinde Schluein zwischen Kilometer 18.50 und Kilometer 18.70 eine leicht angepasste Linienführung, eine Verbreiterung der Strasse sowie einen talseitigen Gehweg vor. Die Schleuisertobelbrücke und die Unterführung "Haus Camenisch" werden ersetzt. Schliesslich soll der Anschluss Sagogn neu gestaltet werden: Die heute spitzwinklige Einmündung der Via Veglia in die Oberalpstrasse soll so umgestaltet werden, dass ein rechtwinkliges Einmünden in die Hauptstrasse möglich ist. Dies bedingt eine Anpassung der kantonalen Verbindungsstrasse Via Veglia auf einer Strecke von rund 40 m sowie der Via Mulina auf einer Strecke von rund 50 m. B. Gegen das Strassenprojekt erhoben unter anderem A.A._ und B.A._ Einsprache. Diese sind Eigentümer der vom neuen Anschluss Sagogn beanspruchten Parzellen Nrn. 841 und 150; auf Parzelle Nr. 841 befindet sich der historische "Gasthof zur Post" (Baute Nr. 48). Am 20. Mai 2014 hiess die Regierung des Kantons Graubünden das Auflageprojekt unter Auflagen gut und erteilte die spezialrechtlichen Bewilligungen. Die Einsprachen von A.A._ und B.A._ hiess sie teilweise gut (hinsichtlich Lärmschutz und Einfriedung des Vorgartens), überwies die Einsprachen hinsichtlich der geforderten Entschädigung an das Tiefbauamt Graubünden und wies die übrigen Einwände ab, soweit sie darauf eintrat. C. Dagegen erhoben A.A._ und B.A._ am 30. Juni 2014 Beschwerde beim Verwaltungsgericht des Kantons Graubünden. Dieses führte am 16. November 2015 einen Augenschein durch und wies die Beschwerde am 17. November 2015 ab. D. Gegen den verwaltungsgerichtlichen Entscheid haben A.A._ und B.A._ am 10. Februar 2016 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, die Entscheide des Verwaltungsgerichts und der Regierung seien aufzuheben und dem Auflageprojekt sei die Genehmigung zu verweigern, soweit es ihre Parzellen betreffe. Das Auflageprojekt sei innerorts so zu redimensionieren, dass die Parzelle Nr. 841 inklusive Vorgarten sowie die Parzelle Nr. 150 durch das Projekt nicht tangiert würden und der historische Strassenverlauf gewahrt werde. Eventualiter sei die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen. E. Das Verwaltungsgericht und die Regierung schliessen auf Abweisung der Beschwerde (soweit darauf einzutreten sei). Das Bundesamt für Strassen (ASTRA) äussert sich als Bundesfachstelle für den Schutz historischer Verkehrswege (Art. 23 Abs. 1 lit. c der Verordnung über den Natur- und Heimatschutz vom 16. Januar 1991 [NHV; SR 451.1]) zum Eingriff in die Via Veglia, die als Wegabschnitt der alten linksrheinischen Kunststrasse von 1842, Objekt GR 71.7.2, als Objekt "historischer Verlauf mit Substanz" im Bundesinventar der historischen Verkehrswege der Schweiz (IVS) verzeichnet ist. F. Die Beschwerdeführer halten in ihrer Replik vom 13. Juni 2016 an ihren Anträgen fest.